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