소문자로 된 문자열 S가 있다고 가정합니다. 각 문자가 최대 한 부분에 나타나도록 이 문자열을 가능한 한 많은 부분으로 분할하고 마지막으로 이러한 부분의 크기를 나타내는 정수 목록을 반환합니다. 따라서 문자열이 "ababcbacadefegdehijhklij"와 같으면 파티션이 "ababcbaca", "defegde", "hijhklij"이기 때문에 출력은 [9,7,8]입니다. 따라서 이것은 각 문자가 많아야 한 부분에 나타나도록 파티션입니다. "ababcbacadefegde", "hijhklij"와 같은 파티션은 S를 더 적은 부분으로 분할하기 때문에 올바르지 않습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- cnt라는 하나의 지도 정의
- 0에서 s 사이의 i에 대해 cnt[s[i]] :=i
- j :=0, 시작 :=0 및 i :=0 및 n :=s의 크기
- 하나의 배열 정의
- 내가
- j :=j 및 cnt[s[i]]의 최대값
- i =j이면 i – start + 1을 ans에 삽입하고 start :=i + 1
- i를 1 증가
예시(C++)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> partitionLabels(string s) {
map <char, int> cnt;
for(int i = 0; i < s.size(); i++)cnt[s[i]] = i;
int j = 0, start = 0;
int i = 0;
int n = s.size();
vector <int> ans;
while(i < n){
j = max(j, cnt[s[i]]);
if( i == j){
ans.push_back(i-start+ 1);
start = i + 1;
}
i++;
}
return ans;
}
};
main(){
Solution ob;
print_vector(ob.partitionLabels("ababcbacadefegdehijhklij"));
} 입력
"ababcbacadefegdehijhklij"
출력
[9,7,8]