Description Link to heading

763.partition-label

Solution Link to heading

solution 1 Link to heading

First, we need traverse the string, record the maximum index of each letter in the string.

Then we need declare a variable right to record the maximum index of letter traversed. When the maximum index is the same as current index, we can partition the string.

solution 2 Link to heading

First, we need traverse the string, record the number of occurrence of each letter, and record whether the letter occur.

Then, we need traverse the string again, if it’s the first time the letter occurs, push(s[i]);, if it is the last time the letter occurs, pop();. If the stack is empty, we can partition the string.

Code Link to heading

code 1 Link to heading 

class Solution {
public:
    vector<int> partitionLabels(string S) {
        int hash[27] = {0}; 
        for (int i = 0; i < S.size(); i++) { 
            hash[S[i] - 'a'] = i;
        }
        vector<int> result;
        int left = 0;
        int right = 0;
        for (int i = 0; i < S.size(); i++) {
            right = max(right, hash[S[i] - 'a']); 
            if (i == right) {
                result.push_back(right - left + 1);
                left = i + 1;
            }
        }
        return result;
    }
};

code 2 Link to heading 

class Solution {
  public:
    vector<int> partitionLabels(string s) {
        vector<int> res;
        int arr[26] = {0};
        int arr_bool[26] = {0};
        int len = 0;
        stack<char> st;
        for (int i = 0; i < s.size(); i++) {
            arr[s[i] - 'a']++;
            arr_bool[s[i] - 'a'] = 1;
        }
        for (int i = 0; i < s.size(); i++) {
            len++;
            arr[s[i] - 'a']--;
            if (arr_bool[s[i] - 'a'] != 0) {
                st.push(s[i]);
                arr_bool[s[i] - 'a'] = 0;
            }
            if (arr[s[i] - 'a'] == 0)
                st.pop();
            if (st.empty()) {
                res.push_back(len);
                len = 0;
            }
        }
        return res;
    }
};