You are given a string s
. We want to partition the string into as many parts as possible so that each letter appears in at most one part.
Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s
.
Return a list of integers representing the size of these parts.
Example 1:
Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits s into less parts.
Example 2:
Input: s = "eccbbbbdec"
Output: [10]
Constraints:
1 <= s.length <= 500
s
consists of lowercase English letters.給定一個字串 s,
希望透過一個字串切割的方式,儘可能把所有相同字元切割在同一個子字串,然後儘可能把不同字元切割到不同子字串
要求寫一個演算法來計算透過上述的切割方式來找到切割後每個子字串的長度
對於每個字元因為希望儘可能切割到同一個子字串
所以需要紀錄每個字元出現的最後位置
這邊以 HashMap lastPos 紀錄每個字元的最後位置