Daily LeetCode Challenge - 1239. Maximum Length of a Concatenated String with Unique Characters

Problem From.
https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/

오늘 문제는 string 으로 이루어져있는 list 가 주어졌다.
그 리스트에서 각 원소를 이어붙였을때, 중복되는 알파벳이 없이 가장 긴 리스트의 길이를 반환하는 문제였다.

처음에 경우의 수를 구하는 알고리즘을 잘못 세워서 잠깐 헷갈렸지만 DFS 를 통해서 금방 해결할 수 있었다.

DFS 속에서 각 원소를 이어붙인 값을 string.toSet() 을 이용하여 중복을 제거한 리스트화 하여, 중복을 제거했을 때 그 길이가 이어붙인 값과 다르면 겹치는 알파벳이 있다고 판단하도록 하였다.

class Solution {
    
    private var answer = 0
    
    fun maxLength(arr: List<String>): Int {
        
        findMax(0, "", arr)

        return answer
    }
    
    private fun findMax(index : Int, letter : String, arr : List<String>) {
        
        if(index >= arr.size) return
        if(letter.toSet().size != letter.length) return
        if(letter.length > answer) answer = letter.length

        for(i in index until arr.size){
            findMax(i, letter + arr[i], arr)
        }

    }
    
}

오늘 문제는 자칫 복잡해 보이지만, DFS 를 이용하여 단계적으로 풀면 금방 풀 수 있는 문제였다.