[ Leetcode ] 763. Partition Labels - Java

 

 

 

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.

 

Solution

 

 
 class Solution {
    public List<Integer> partitionLabels(String S) {
        int[] positions = new int[26];
        List<Integer> answer = new ArrayList();
    
        for(int i=0; i< S.length(); i++){
            positions[S.charAt(i) - 'a'] = i;
        }
        
        for(int i=0; i< S.length(); i++){
            
            int end = positions[S.charAt(i) - 'a'];
            int count = 0;
            
            for(int j=i; j<= end; j++){
                int position = S.charAt(j) - 'a';
                if(positions[position] > end){
                    end = positions[position];
                }
                count++;
            }
            i += count - 1;
            answer.add(count);
        }
        return answer;
    }
 }
 

1. 문자열 하나마다 제일 마지막 포지션을 저장한다

2. 문자열에 대해서 마지막 포지션까지 카운트를 세면서 그 사이값이 더 뒤의 포지션값을 가지고 있다면 그 값으로 end값을 대체한다

3. 카운트보다 하나 적은 위치로 다시 i를 세팅해준다

 

99.36% ! 뿌듯 100%되기가 어렵다