“This is the 15th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

[B] [C] [D]

The string S consists of lowercase letters. We want to divide the string into as many fragments as possible, with the same letter appearing in at most one fragment. Returns a list representing the length of each string fragment.

Example:

Input: S = "ababcbacadefegdehijhklij" output: [9,7,8] explanation: partition result is "ababcbaca", "defegde", "hijhklij". Each letter appears in at most one fragment. The division of "ababcbacadefegde", "hijhklij" is wrong because the number of segments divided is small.Copy the code

Tip:

  • SThe length of the[1, 500]In between.
  • SContains only lowercase letters'a' 到 'z' 。

Their thinking

In this case, the same letter can only appear in one fragment. Therefore, for a single letter, we can find the position where it first appears and the position where it last appears. Such an interval can be divided into a fragment to ensure that it only appears in one fragment. However, since there may be other letters in such an interval, we also need to ensure that other letters only appear in a fragment. How can we solve this problem? Here we can iterate over the input string, recording the first occurrence of each letter and the last occurrence of each letter. Once the array is iterated, we have the beginning and end positions of each letter. Because we are traversing the array from front to back, the starting position of each interval is monotonically increasing. At this time, we record the maximum value of the end position of the previous letter interval. When the start value of the subsequent interval is greater than the maximum value of the end value of the previous interval, it means that the letters in the previous interval will not appear in the subsequent interval. At this time, the previous interval can be divided into a separate segment. The length of such a fragment is the maximum end value of all intervals minus the minimum start value +1. Each time we find a fragment, we compute the length of the fragment and insert it into the result array, and when we’re done iterating through all the letter intervals, we get our answer.

Code implementation

Var partitionLabels = function (s) {let map = new map (); For (let I = 0; i < s.length; i++) { if (map.has(s[i])) map.get(s[i])[1] = i else map.set(s[i], [i, I])} const res = [] let pre = 0, ForEach ((item) => {const [a, b] = item // If the start index of the current letter is within the range to be integrated, If (a <= end) end = math.max (end, Else {res.push(end - pre + 1) // initializes the start and end subscripts of the next interval to be merged pre = a end = b}}) // Inserts the last interval to be merged into the result array Res.push (end-pre + 1) return res}Copy the code

At this point we are done with Leetcode -763- dividing letter intervals

If you have any questions or suggestions, please leave a comment! 👏 🏻 👏 🏻 👏 🏻