[leetcode 763] Partition Labels

문자열 s을 쪼갤 때 각 알파벳들이 한 구간에만 나오도록 최대한 많이 쪼개기

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.

 

- 문제 이해가 어려웠다.

- 문자열을 돌면서 처음 위치와 마지막 위치를 기록한다. 알파벳이 한번만 나오는 경우도 있으므로 처음 위치를 등록할 때 마지막 위치도같이 등록. 다음 알파벳이 나올 때마다 마지막 위치 업뎃

- 다시 문자열을 처음부터 돌면서 i에 해당하는 문자열의 마지막 등장 위치까지 loop를돈다.

 -> 마지막 등장 위치가 증가할 때마다 업데이트 시킨다.

- loop를 다 돌고 answer에 푸쉬

 

class Solution {
public:
    vector<int> partitionLabels(string S) {
        vector<int> answer;
        
        if(S.length() == 0){
            answer.push_back(0);
            return answer;
        }
        
        int start[26];
        int end[26];
        memset(start, -1 ,sizeof(start));
        memset(end, -1, sizeof(end));
        
        for(int i=0; i<S.length(); i++){
            if(start[S[i]-'a'] == -1){
                start[S[i]-'a'] = i;
                end[S[i]-'a'] = i;
            }else{
                end[S[i]-'a'] = i;
            }
        }
         
        int endIdx, tmp;
        for(int i=0; i<S.length(); i++){
            endIdx = end[S[i]-'a'];
            tmp = endIdx - i;
            for(int j=i; j<endIdx; j++){
                if(end[S[j]-'a'] > endIdx){
                    endIdx = end[S[j]-'a'];
                }
            }
            tmp = endIdx -i + 1;
            answer.push_back(tmp);
            i = endIdx;
        }
        return answer;
    }
};