LeetCode 763. Partition Labels

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.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

Return a list of integers representing the size of these parts.

https://leetcode.com/problems/partition-labels/

Partition Labels - LeetCode

 

문자열을 끊되, 중복되지 않는 한에서 가장 많이 끊을 수 있는 경우의 수를 구하는 문제이다.

이 문제를 어떻게든 풀고싶어서. . 며칠을 고민하고 풀었는데

간단하지만 직관적인 해설방법을 역시나 찾았다 ㅎㅎ;

  public static List<Integer> partitionLabels(String s) {
        Map<Character, Integer> map = new HashMap();
        for(int i=0; i<s.length(); i++) {
            char ch = s.charAt(i);
            map.put(ch,i);
        }

        List<Integer> res = new LinkedList();
        int prev = -1;
        int max = 0;

        for(int i=0; i<s.length(); i++) {
            char ch = s.charAt(i);
            max = Math.max(max, map.get(ch));

            // 끝에 달았을때
            if(max == i) {
                res.add(max - prev) ;
                prev = max;
            }
        }
        return res;
    }

참고 코드