- Problem

2405. Optimal Partition of String

Return the minimum number of substrings in such a partition
이 조건을 제대로 파악 못해서 삽질했다. 문제를 제대로 읽자.

파티션의 최소 문자열 수를 얻기 위해선, 문자열s를 순회하며 중복된 문자(character)가 나올 때 마다 문자열을 끊어주면 된다.

- 내 풀이

class Solution:
    def partitionString(self, s: str) -> int:
        partitioned_string = set()
        minimum_substrings = 0

        for c in s:
            if c in partitioned_string:
                partitioned_string.clear()
                minimum_substrings += 1
            partitioned_string.add(c)

        return minimum_substrings + 1

- 결과

• 시간 복잡도: O(N)
• 공간 복잡도: O(1)
  - s는 영소문자로만 주어지고, 중복을 허용하지 않는다. 따라서 공간 복잡도는 일정하다.