Leetcode scribble notes 763. Divide the letter range (medium)

1. 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 .

2. Code ：

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int last[26];
        int length = s.size();

        // Find the last position of each character 
        for(int i = 0; i < length; ++i){
            last[s[i] - 'a'] = i;
        }
        int start =0, end = 0;
        vector<int> sss;    // Store partitioned data 
        for(int i = 0; i < length; ++i){
            end = max(end, last[s[i] - 'a']);
            if(end == i){
                sss.push_back(end-start+1);
                start = end + 1;
            }
        }
        return sss;
    }
};

3. Their thinking ：

Input ：S = "ababcbacadefegdehijhklij"
Output ：[9,7,8]
explain ：
The result is "ababcbaca", "defegde", "hijhklij".

Combined with the above example ！！

The same letter can only appear in the same segment , Also divide the number of strings as much as possible , Then the position of the last occurrence of each letter , It is possible to divide the position of the string ,( The position of the two divisions in the example is a and e The last place ) In the process of traversing a string , By comparing the last position of the characters that have been traversed , The most backward position must be the interception end ,（ For example, in the first string , Letter a The last place where the appears is s[8],s[0] To s[8] The last positions of the letters contained between are s[8] Before ） And the end of the previous string is the beginning of the next string (s[8] Is the end of the first string ,s[9] Is the beginning of the next string ).

4. Code ：

        @ First step ： Find the last position of each character , Stored in an array .

        @ The second step ： Define two int Type variable start and end, The initial values are all 0,start Used to store the beginning of a string ,end Used to store the farthest end of the string that has been traversed . Update every character you traverse end Value , When end When the value is exactly the current traversal position , It's time to intercept the string , Then the intercepted length is end - start + 1, And then put (end + 1) Assign a value to start, Repeat operation .