[2024] Day23. 1239. Maximum Length of a Concatenated String with Unique Characters

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 1월 23일 (화)
Leetcode daily problem

1239. Maximum Length of a Concatenated String with Unique Characters

https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/description/?envType=daily-question&envId=2024-01-23

Problem

문자열 배열 arr이 주어질 때, 배열 arr의 요소인 각 문자열들은 arr의 일부 부분 문자열을 연결하여 고유한 문자를 이룰 수 있다.
이 때 배열의 요소들을 조합해서 고유한 문자를 이루는 s의 최대 길이를 반환한다.

부분 문자열은 다른 배열에서 일부 또는 전혀 삭제하지 않고 남은 요소의 순서를 변경하지 않고 생성된다.

예를 들어 arr = ['aa','bb'] 는 조합으로 고유 문자열일 이루지 못하므로 0을 반환하고 arr = ['a','bc','d'] 라면 'abcd' 로 고유 부분 문자열 최대값인 3을 반환하면 된다.

Solution

backtracking

해당 문제를 주어진 배열을 탐색하면서, 해당 배열 내의 문자열들을 조합해서 고유한 문자열로 구성되어 있는지 확인 한 후 되어 있다면 maxLen을 업데이트 하는 식으로 판단한다.

Code

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        maxLen = 0
        words = ['']

        for word in arr:
            for i in range(len(words)):
                tmp = word + words[i]
                if len(tmp) == len(set(tmp)):
                    words.append(tmp)
                    maxLen = max(maxLen, len(tmp))

        return maxLen  

Complexicity

시간 복잡도

주어진 문자열 배열 arr에 대한 두 개의 이중 포문으로 외부 루프는 주어진 배열의 모든 단어를 반복하고, 내부 루프는 현재까지 생성된 문자열 배열 words의 모든 단어와 각각을 결합한다. 내부 루프에서는 문자열 결합, 길이 확인, 중복 확인이 이루어진다.

총 단어 수를 n이라고 할 때, 내부 루프에서 각 문자열 조합에 대해 문자열의 평균 길이를 k이라 하고 O(l)의 작업이 수행된다.
따라서 전체 시간 복잡도는 O(n k 2^k)입니다.

공간 복잡도

공간 복잡도는 생성된 문자열 배열 words의 크기에 의해 결정되는데, 최악의 경우, 모든 가능한 부분 문자열이 포함된다고 가정한다면, words 배열의 크기는 2^k가 된다. 여기서 k는 문자열의 평균 길이이고, 최종 공간 복잡도는 O(2^k)이다.

---

해당 풀이를 chatgpt에게 물어봤는데 그녀석은 DFS로 풀었다.

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        
        def is_unique(s):
            return len(s) == len(set(s))

        def backtracking(idx, curWord):
            nonlocal maxLen
            maxLen = max(maxLen, len(curWord))

            for i in range(idx, len(arr)):
                if is_unique(curWord + arr[i]):
                    backtracking(i, curWord+arr[i])

        
        maxLen = 0
        backtracking(0, '')
        return maxLen

위 코드의 시간복잡도는

주어진 문자열 배열 arr의 모든 가능한 부분 문자열 조합을 찾기 위해 백트래킹이 사용되고, 각 단계에서 현재 부분 문자열에 문자를 추가할지 말지를 결정하므로 모든 경우의 수를 고려하므로, 전체 시간 복잡도는 O(2^n* n)이다
여기서 n은 문자열 배열의 총 길이이며, 2^n은 모든 가능한 부분 문자열의 경우의 수를 나타냅니다.

공간복잡도는 재귀 호출 스택에 따라 결정되며, 재귀 호출 스택의 깊이인 O(n)으로 총 문자열 배열의 길이인 O(n)이다.