[LC] 763. Partition Labels

[seungriyou]

763. Partition Labels (similar to #116)

Approach

Idea 1: Sorting & Greedy

문제를 잘 이해해보면 결국 overlapped intervals를 merge 하는 문제와 동일하기 때문에, #46 문제의 로직을 그대로 사용할 수 있다.

이때, intervals는 s의 각 문자마다 맨 처음 & 마지막으로 등장하는 인덱스를 찾아 직접 구성하면 된다.

# intervals 오름차순 정렬
intervals.sort()

# overlapped intervals 합치기
res = []
for s, e in intervals:
    # non-overlap
    if not res or res[-1][1] < s:
        res.append([s, e])
    # overlap
    else:
        res[-1][1] = max(res[-1][1], e)

Idea 2: Two Pointer (w/o Sorting) 📌

ref: https://leetcode.com/problems/partition-labels/solutions/298474/python-two-pointer-solution-with-explanation

two pointer를 사용하면 sorting 없이 풀 수 있기 때문에 TC를 O(nlogn) 에서 O(n)으로 줄일 수 있다.

우선, 각 문자가 마지막으로 등장하는 인덱스만 hash map ends에 기록해두고, 현재 확인 중인 non-overlapping interval의 가능한 범위를 lo, hi 라는 pointer로 트래킹한다.

# 각 문자의 가장 마지막 index 기록
ends = {c: i for i, c in enumerate(s)}

# two pointers (for tracking last non-overlapping interval)
lo = hi = 0

그리고 s를 순회하면서 다음의 로직을 수행한다.

1. 지금 보고 있는 문자가 가장 마지막으로 등장하는 인덱스 ends[c]와 hi를 비교하여, 현재 확인 중인 non-overlapping interval의 hi를 업데이트 한다.
2. 만약 현재 문자가 현재 확인 중인 non-overlapping interval의 마지막 문자(= 인덱스 i가 hi) 라면 res에 기록한다.

res = []

for i, c in enumerate(s):
    # 새롭게 찾을 non-overlapping interval의 hi 업데이트
    hi = max(hi, ends[c])

    # 만약 현재 문자가 non-overlapping interval의 마지막 문자라면 기록
    if i == hi:
        res.append(hi - lo + 1)
        lo = hi + 1

Complexity

• Time: (sorting) O(nlogn) / (two-pointer) O(n)
• Space: (sorting) O(n) / (two-pointer) O(26) (s consists of lowercase English letters)