문제
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.
Return a list of integers representing the size of these parts.
제한사항`
- 1 <= s.length <= 500
- s consists of lowercase English letters.
입출력 예
1
2
3
4
5
6
7
8
| 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.
|
1
2
3
4
| Example 2:
Input: s = "eccbbbbdec"
Output: [10]
|
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
vector<int> partitionLabels(string s) {
std::vector<int> res;
std::map<char, int> items;
for (auto i = 0 ; i < s.size() ; ++i) {
items[s[i]] = i;
}
// hash에 저장되어있는 범위의 최대 인덱스와
// 현재 index가 같을때
// 하나의 sub string이 됨
int index = 0;
int offset = 0;
for (auto i = 0 ; i < s.size() ; ++i) {
index = std::max(items[s[i]], index);
if (i == index) {
res.push_back(i - offset + 1);
offset = i + 1;
}
}
return res;
}
};
|
