[DSA][Greedy] 07. Partition Labels

LeetCode 763

 

07. 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.
For example, the string "ababcc" can be partitioned into ["abab", "cc"], but partitions such as ["aba", "bcc"] or ["ab", "ab", "cc"] are invalid.

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.

 

 

[아이디어]

- 알파벳별로 문자열에서의 등장 범위를 구하면, 이를 서로 겹치지 않게 나누는 구간 문제로 해석할 수 있다.

 

 

[풀이 1] Greedy

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last = {c: i for i, c in enumerate(s)}
        res = []
        start = end = 0
        for i, c in enumerate(s):
            end = max(end, last[c])
            if i == end:
                res.append(end - start + 1)
                start = i + 1
        return res

문자열에서 각 알파벳의 시작 위치와 끝 위치를 기록하면, 이 문제는 서로 겹치지 않는 구간(interval)을 구하는 문제로 바꿔서 생각할 수 있다.  2025.09.03 - [자료구조와 알고리즘] - [DSA][Intervals] 02. Merge Intervals

 

하지만 실제로는 시작 인덱스 정보가 없어도 충분하다. 각 문자의 마지막 등장 위치만 미리 알고 있다면, 문자열을 순회하면서 현재 보고 있는 구간의 끝(end)을 "지금까지 등장한 문자들 중 가장 마지막 인덱스"로 갱신할 수 있다.
그리고 현재 인덱스 i가 그 end에 도달하는 순간, 하나의 파티션이 완성된다.

 

⏱️ 시간복잡도

배열을 한 번만 순회하므로 시간 복잡도는 O(n)이다.

🧠 공간복잡도

문자 종류(유니크한 알파벳)의 개수만큼 추가 공간이 필요하므로 공간 복잡도는 O(m)이다.