Problem link
https://leetcode.com/problems/partition-labels/
Problem Summary
문자열을 각 문자들이 최대 한 덩어리에만 있도록 나눠야 한다. 최대한 많이 나눌 때의 덩어리 개수를 구하는 문제.
Solution
잘 생각해보면 한 덩어리에만 있어야 한다는 것은 다음 덩어리에는 해당 문자가 나타나서는 안 된다는 것이다. 다음 문자가 어디 있는지 map을 통해 위치를 저장해두고 현재 덩어리의 모든 문자가 뒤에 나타나지 않으면 한 덩어리로 묶을 수 있다.
위치는 하나만 있으면 되므로 문자의 마지막 위치를 저장해주면 된다.
Source Code
from typing import List
class Solution:
def partitionLabels(self, s: str) -> List[int]:
pos = {}
for i in range(len(s)):
pos[s[i]] = i
ans = []
chunk = []
for i in range(len(s)):
chunk.append(s[i])
split = True
for j in range(len(chunk)):
if pos[chunk[j]] > i:
split = False
break
if split:
ans.append(len(chunk))
chunk = []
return ans