A string S
of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and 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.
Note:
S
will have length in range[1, 500]
.S
will consist of lowercase English letters ('a'
to'z'
) only.
A:
挺好的题。 就是每次找到最右边。
class Solution { public: vector<int> partitionLabels(string S) { int n = S.length(); unordered_map<char, int> M; for(int i =0;i<n;i++){ M[S[i]] = i; } vector<int> res; int start = 0; while(start < n){ int end = M[S[start]]; for(int i =start;i<=end;i++){ end = max(end, M[S[i]]); } res.push_back(end-start+1); start = end+1; } return res; } };
No comments:
Post a Comment