Leetcode 1593. Split a String Into the Max Number of Unique Substrings

문제

Given a string s, 
return the maximum number of unique substrings that the given string can be split into.

You can split string s into any list of non-empty substrings, 
where the concatenation of the substrings forms the original string. 
However, you must split the substrings such that all of them are unique.

A substring is a contiguous sequence of characters within a string.

• 문자열 s가 주어진다.
• 주어진 문자열을 여러개의 서브 문자열로 분리할때, 겹치는 서브 문자열이 없도록 한다면
• 서브 문자열의 갯수가 가장 많게 했을때, 그 갯수를 리턴하시오.

예시

"ababccc"

• 서브 문자열은 아래와 같이 나눌수 있다.
  • a
  • b
  • ab
  • c
  • cc
• 최대 5개의 문자열로 분리될수 있기 때문에, 정답은 5이다.

제한

• $1 <= s.length <= 16$
• s는 소문자 영어만을 포함한다.

풀이법

• 백트래킹을 사용한다.
• set을 이용해 현재까지 들어왔던 모든 서브 문자열을 트래킹한다.

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        appeared = set()

        def tracking(i: int):

            if i == len(s):
                return 0

            app = ""

            ans = 0

            # 현재 인덱스로 부터 만들수 있는 모든 서브 문자열에 대해 검사한다.
            for i in range(i, len(s)):
                ch = s[i]
                app = app + ch
                # 만약 해당 서브 문자열이 등장하지 않았다면, 추가해 본다.
                if app not in appeared:
                    appeared.add(app)
                    ans = max(ans, tracking(i + 1) + 1)
                    appeared.remove(app)

            return ans

        return tracking(0)