2405. Optimal Partition of String

[zeikar]

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