Topic:

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 only one of them. Returns a list representing the length of each string fragment.

Example:

  1. Example 1:
Enter: S ="ababcbacadefegdehijhklij"

Output: proposal [9]

Explanation:

The partition result is"ababcbaca"."defegde"."hijhklij".

Each letter appears in at most one fragment.

like"ababcbacadefegde"."hijhklij"The partition of is wrong because the number of segments divided is small.

Copy the code

Tip:

  • The length of S is between [1, 500].
  • The S contains only lowercase letters ‘a’ through ‘z’.

The topic

Ideas:

Train of thought
'a'= > 8,

'b'= > 5,

'c'= > 7,

'd'= > 14,

'e'= > 15,

'f'= > 11,

'g'= > 13,

'h'= > 19,

'i'= > 22,

'j'= > 23,

'k'= > 20.

'l'= > 21

Copy the code

Find the last position of each character and search for each character individually,

If you encounter characters farther back in the last position of the element before finding the last position of the element, extend the length to be cut,

The position of last occurrence of all characters is in the current fragment until it is intercepted

The topic
/ * *

 * @param {string} S

 * @return {number[]}

* /

var partitionLabels = function(S) {

  let map = new Map(),

    _result = [],

    index = 0.

    maxIndex = 0

  for (let i = 0; i < S.length; i++) {

    map.set(S[i], i)

  }

  let i = 0

  while (i < S.length) {

    maxIndex = Math.max(map.get(S[i]), maxIndex)

    if (i == maxIndex) {

      _result.push(i - index + 1)

      index = i + 1

    }

    i++

  }

  return _result

}

Copy the code

Blog: Front end little bookboy

Every day a daily problem, write the solution of the problem will be updated to the public account one day a big Lee column welcome to pay attention to the message

Public number: front end little bookboy