leetcode763：划分字母区间

题目链接

leetcode

题目描述

给你一个字符串 s 。把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。

C++ 代码

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

/*
    同一个字母只能出现在同一个片段，
    同一个字母的第一次出现的下标位置和最后一次出现的下标位置，出现在同一个片段。
    因此，遍历字符串得到每个字母最后一次出现的下标位置，使用贪心的方法。

    寻找每个片段可能的最小结束下标，保证每个片段的长度是符合要求的最短长度。
    若取更短的片段，则一定会出现同一个字母出现在多个片段中的情况。
    由于每次取的片段都是最短的，所以片段数是最多的。
    
    时间复杂度：O(n)
        其中 n 是字符串的长度，遍历字符串两次。
        第一次遍历时记录每个字母最后一次出现的下标位置，
        第二次遍历时进行字符串的划分。
    空间复杂度：O(C)
        其中 C 是字符串中的字符集。
        字符串只包含小写字母，C = 26。
*/
class Solution {
public:
    vector<int> partitionLabels(string s) {
        // 记录每个字符最后出现的位置
        unordered_map<char, int> lastPos;
        for (int i = 0; i < s.size(); i++) {
            lastPos[s[i]] = i;
        }

        vector<int> result;
        int start = 0, end = 0;
        for (int i = 0; i < s.size(); i++) {
            end = max(end, lastPos[s[i]]); // 更新当前区间的最远右边界
            if (i == end) { // 找到了一个完整的区间
                result.push_back(end - start + 1);
                start = end + 1; // 下一个区间的起点
            }
        }

        return result;
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    Solution solution;
    vector<string> s_cases = {
        "ababcbacadefegdehijhklij",
        "eccbbbbdec"
    };

    for (const auto& s : s_cases) {
        cout << "Input: \"" << s << "\"" << endl;
        cout << "Output: ";
        vector<int> result = solution.partitionLabels(s);
        printArray(result);
        cout << endl;
    }

    return 0;
}