파이썬에서 문자열을 고유한 하위 문자열의 최대 수로 분할하는 프로그램을 찾는 프로그램

<시간/>

문자열 s가 있다고 가정하고 주어진 문자열을 분할할 수 있는 고유한 하위 문자열의 최대 수를 찾아야 합니다. 문자열 s를 비어 있지 않은 하위 문자열 목록으로 분할하여 하위 문자열을 연결하여 원래 문자열을 형성할 수 있습니다. 그러나 부분 문자열을 모두 같도록 분할해야 합니다.

따라서 입력이 s ="pqpqrrr"과 같으면 출력은 ['p', 'q', 'pq', 'r', 'rr']처럼 분할할 수 있기 때문에 5가 됩니다. ['p', 'q', 'p', 'q', 'r', 'rr']처럼 분할하면 'p'와 'q'가 여러 번 있기 때문에 유효하지 않습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

res :=요소가 하나만 있는 목록 0
dfs() 함수를 정의합니다. 이것은 새로운 빈 세트인 s, 경로를 취합니다.
s가 비어 있으면
- res[0] :=최대 res[0] 및 경로 크기
- 반환
범위 1에서 s까지의 i에 대해 다음을 수행합니다.
- x :=s의 하위 배열[인덱스 0에서 i-1까지]
- x가 경로에 없으면
  - dfs(s의 부분 문자열[인덱스 i에서 끝까지], 경로 U {x})
메인 방법에서 다음을 수행하십시오 -
dfs
반환 결과[0]

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def solve(s):
   res = [0]
   def dfs(s, path=set()):
      if not s:
         res[0] = max(res[0], len(path))
         return
      for i in range(1, len(s)+1):
         x = s[:i]
         if x not in path:
            dfs(s[i:], path|{x})
   dfs(s)
   return res[0]
s = "pqpqrrr"
print(solve(s))

입력

"pqpqrrr"