Leetcode (763) -- dividing letter ranges

Leetcode（763）—— Division of alphabet

subject

character string S It's made up of lowercase letters . We're going to divide this string into as many pieces as possible , The same letter can appear in at most one segment . Returns a list representing the length of each string fragment .

Example ：

Input ：S = “ababcbacadefegdehijhklij”
Output ：[9,7,8]
explain ：
The result is “ababcbaca”, “defegde”, “hijhklij”.
Each letter appears in at most one segment .
image “ababcbacadefegde”, “hijhklij” The division is wrong , Because the number of segments is small .

Tips ：

• S The length of is $[1,500]$ Between .
• S Contains only lowercase letters ‘a’ To ‘z’ .

Answer key

The key ： Before processing the array, you can count the information （ frequency 、 Number 、 First or last position, etc ） It can reduce the difficulty

Method 1 ： greedy

Ideas

​​   Because the same letter can only appear in the same segment , Obviously, the first and last subscript of the same letter must appear in the same segment . So you need to traverse the string , Get the last subscript of each letter .

​​   After getting the last subscript position of each letter , You can use greedy methods to divide a string into as many fragments as possible , The specific methods are as follows .

• Traversing the string from left to right , Maintain the starting subscript of the current fragment while traversing $\text{start}$ And end subscript $\text{end}$, At the beginning $\text{start}=\text{end}=0$.
• For each letter accessed $c$, Get the last subscript position of the current letter ${\text{end}}_c$, The ending subscript of the current clip must not be less than ${\text{end}}_c$, So make $\text{end}=\max (\text{end},{\text{end}}_c)$.
• When accessing subscripts $\text{end}$ when , End of current fragment access , The subscript range of the current clip is $[\text{start},\text{end}]$, The length is $\text{end}-\text{start}+1$, Adds the length of the current fragment to the return value , Then make $\text{start}=\text{end}+1$, Keep looking for the next clip .
• Repeat the process , Until the string is traversed .

​​   The above method uses the greedy idea to find the minimum possible ending subscript of each fragment , Therefore, it can be ensured that the length of each segment must be the shortest length that meets the requirements , If you take a shorter segment , The same letter must appear in multiple clips . Because the segment taken each time is the shortest segment that meets the requirements , Therefore, the number of fragments obtained is also the largest .

​​   Since the end of each segment access is marked by access to the subscript $\text{end}$, So for each segment , It can ensure that every letter in the current clip must be in the current clip , It can't appear in other clips , It can ensure that the same letter will only appear in the same segment .

perhaps

1. Traverse the string from scratch , And count the last position of each character ;
2. Use a variable MaxPos preservation The maximum value in the last occurrence position of the currently scanned character . Then traverse the string again from the beginning , And update the MaxPos Value , If you find the current subscript and MaxPos Equal , The split point is found .

For example, below ： Scan first “ababc” Then the scanned characters are ‘a’ ‘b’ ‘c’, The maximum value in the last position , namely MaxPos by 8. When it comes to “def” when , The scanned characters are ‘d’ ‘e’ ‘f’,MaxPos by 15. Because the characters ‘a’ ‘b’ ‘c’ It is already the character of the previous interval , Separated .

Code implementation

Leetcode Official explanation ：

class Solution {
    
public:
    vector<int> partitionLabels(string s) {
    
        vector<int> res;
        int last[26];
        int n = s.size();
        for (int i = 0; i < n; i++)
            last[s[i]-'a'] = i; // Record each letter in s Last position in 
        int start = 0, end = 0;
        for (int i = 0; i < n; i++){
    
            end = max(end, last[s[i]-'a']);
            if (end == i){
    
                res.push_back(end - start + 1);
                start = end + 1;
            }
        }
        return res;
    }
};

My own ：

class Solution {
    
public:
    vector<int> partitionLabels(string s) {
    
        //  The general problem is ： Find the most intervals , The same letter can only appear in the same interval 
        //  Regarding the starting point and ending point of the same letter as the left and right end points of an interval 
        //  This question translates to ： Treat overlapping intervals as the same interval , Get the maximum number of intervals 
        unordered_map<char, int> letter;
        vector<vector<int>> section;
        int size = s.size();
        for(int n = 0; n < size; n++){
    
            if(letter.count(s[n]) == 0){
    
                section.push_back({
    n, n});
                letter.emplace(s[n], section.size()-1);
            }else section[letter[s[n]]][1] = n;
        }
        // for(auto& it: letter) cout << it.first << " :" << section[it.second][0] << " " << section[it.second][1] << endl;
        //  There is no need to sort by left endpoint in ascending order , Because the previous cycle is to save from the left endpoint 0 To size-1 The saved 
        vector<int> ans;
        vector<vector<int>> tmp;
        size = section.size();
        for(int n = 0; n < size; n++){
    
            //  At the beginning or between new areas, it does not overlap with the previous interval , Create a new interval , And calculate the length of the previous interval 
            if(tmp.empty() || section[n][0] >= (*tmp.rbegin())[1]){
    
                if(!tmp.empty()) ans.push_back((*tmp.rbegin())[1] - (*tmp.rbegin())[0] + 1);
                tmp.push_back({
    section[n][0], section[n][1]});
            }else (*tmp.rbegin())[1] = max((*tmp.rbegin())[1], section[n][1]);
            if(n == size-1) ans.push_back((*tmp.rbegin())[1] - (*tmp.rbegin())[0] + 1);
        }
        return ans;
    }
};

Complexity analysis

Time complexity ：$O(n)$, among nn Is the length of the string . You need to traverse the string twice , Record the subscript position of the last occurrence of each letter during the first traversal , During the second traversal, the string is divided .
Spatial complexity ：$O(\mid \Sigma \mid )$, among $\Sigma$ Is the character set in the string . In this question , The string contains only lowercase letters , therefore $|\Sigma |=26$.