파이썬으로 고유 문자로만 이루어진 최장 연결 문자열의 길이 구하기

문제 개요

문자열 리스트 words가 주어졌을 때, 리스트의 부분 수열을 골라 이어 붙여 하나의 문자열을 만든다고 가정해 봅시다. 이때 최종 문자열에는 동일한 문자가 두 번 이상 나타나서는 안 되며, 즉 모든 문자가 고유해야 합니다. 우리가 구해야 하는 값은 이러한 조건을 만족하는 연결 문자열 중 가장 긴 것의 길이입니다.

예를 들어 입력이 words = ["xyz", "xyw", "wab", "cde"]라면 정답은 9입니다. "xyz", "wab", "cde"를 순서대로 이어 붙인 "xyzwabcde"가 서로 겹치지 않는 9개의 문자로 이루어져 있기 때문입니다. 반면 "xyw"는 "xyz"와 문자 x, y가 중복되므로 함께 선택할 수 없습니다.

접근 방법

이 문제는 백트래킹(backtracking) 재귀로 깔끔하게 해결할 수 있습니다. 각 단어마다 두 가지 선택지, 즉 '현재 문자열에 추가하기' 또는 '건너뛰기'를 모두 시도하되, 추가했을 때 중복 문자가 발생하는 경우는 가지치기(pruning)하면 됩니다.

구체적인 절차는 다음과 같습니다.

정답을 저장할 변수 ans를 0으로 초기화합니다.
재귀 함수 recur(i, cur)를 정의합니다. 여기서 i는 현재 확인 중인 단어의 인덱스, cur은 지금까지 만든 문자열입니다.
i가 words의 길이와 같아지면 탐색이 끝난 것이므로, ans와 cur의 길이 중 더 큰 값으로 ans를 갱신하고 반환합니다.
먼저 현재 단어를 건너뛰는 경우인 recur(i + 1, cur)을 호출합니다.
words[i] 자체에 중복 문자가 없고, cur + words[i] 역시 모든 문자가 고유하다면 단어를 추가하는 경우인 recur(i + 1, cur + words[i])도 호출합니다.

문자열에 중복이 있는지는 set(s)의 길이와 s의 길이를 비교하면 간단히 판별할 수 있습니다. 집합은 중복을 제거하므로 두 길이가 같다면 모든 문자가 고유하다는 의미입니다.

구현 예시

class Solution:
    def solve(self, words):
        ans = 0

        def is_all_unique(s):
            return len(set(s)) == len(s)

        def recur(i=0, cur=""):
            nonlocal ans
            if i == len(words):
                ans = max(ans, len(cur))
                return

            recur(i + 1, cur)
            if is_all_unique(words[i]) and is_all_unique(cur + words[i]):
                recur(i + 1, cur + words[i])

        recur()
        return ans

ob = Solution()
words = ["xyz", "xyw", "wab", "cde"]
print(ob.solve(words))

입력

["xyz", "xyw", "wab", "cde"]

출력

복잡도 분석

각 단어마다 포함하거나 제외하는 두 가지 선택이 존재하므로 최대 2^n개의 조합을 탐색하게 됩니다. 따라서 전체 시간 복잡도는 대략 O(2^n × L)입니다(n은 단어 개수, L은 평균 문자열 길이). 재귀 호출의 깊이는 단어 개수에 비례하므로 공간 복잡도는 O(n)입니다.