Problem link
https://leetcode.com/problems/optimal-partition-of-string/
Problem Summary
문자열을 겹치는 문자 없는 substring으로 나눌 때 최소 횟수를 구하는 문제.
Solution
그리디 적으로 생각하면 바로 풀린다. 문자열을 최대한 크게 나눈다고 생각하면 된다. 그런 다음 나눌 수밖에 없는 부분을 나눈다.
즉, 이미 나온 문자가 나타나면 새로운 substring으로 나눠야만 한다.
Source Code
class Solution:
def partitionString(self, s: str) -> int:
found = defaultdict(bool)
ans = 1
for l in s:
if found[l]:
found = defaultdict(bool)
ans += 1
found[l] = True
return ans