Leetcode 763. partition labels divide alphabetic intervals (medium)

One 、 The main idea of the topic

label : greedy

https://leetcode.cn/problems/partition-labels

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

Two 、 Their thinking

A string S, Split it into substrings as much as possible , The condition is that each character can only appear in one substring at most . In the example above , character string S There are multiple a, these a Must only be in the first substring , Letter e Appears in the second substring . The difficulty of this problem is how to find the breakpoint of the string , That is, the position of splitting into substrings . Look at the above examples , Once a letter appears many times , Then the last occurrence position must be in the current substring , Letter a,e,j They are the ending letters in the three substrings . So we focus on the last position of each letter , We can use a Map To establish the mapping between the letter and its last occurrence , After the mapping is established , You need to start traversing the string S, We maintain a start Variable , Is the starting position of the current substring , One more last Variable , Is the end position of the current substring , Whenever we traverse to a letter , Need to be in Map Extract its last position , Because once the current substring eats a letter , It must eat all the same letters , So we keep updating with the last position of the current letter last Variable , Only when i and last It's the same , namely i=last when , The current substring contains the last position of all the letters that have appeared , That is, the following string will not have the letters that appeared before , At this time, it should be the disconnected position , We add the substring length to the result .

3、 ... and 、 How to solve the problem

3.1 Java Realization

public class Solution {
    
    public List<Integer> partitionLabels(String s) {
    
        Map<Character, Integer> map = new HashMap<>();
        char[] cArr = s.toCharArray();
        for (int i = 0; i < cArr.length; i++) {
    
            map.put(cArr[i], i);
        }

        List<Integer> res = new ArrayList<>();
        int start = 0;
        int last = 0;
        for (int i = 0; i < cArr.length; i++) {
    
            last = Math.max(map.get(cArr[i]), last);
            if (i == last) {
    
                res.add(last - start + 1);
                start = last + 1;
            }
        }

        return res;
    }
}

Four 、 Summary notes

• 2022/7/28 Clear your mind , The code comes out naturally