1239. Maximum Length of a Concatenated String with Unique Characters (고유한 문자로 연결된 문자열의 최대 길이) C#

You are given an array of strings arr. A string s is formed by the concatenation of a subsequence of arr that has unique characters.

Return the maximum possible length of s.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

 

문자열 배열 arr가 주어집니다. 문자열 s는 고유한 문자를 가진 arr의 부분 수열을 연결하여 형성됩니다.

 

s가 가능한 최대 길이를 반환합니다.

 

부분 수열은 나머지 요소의 순서를 변경하지 않고 일부 요소를 삭제하거나 전혀 삭제하지 않고 다른 배열에서 파생될 수 있는 배열입니다

 

 

예시 1:

입력: arr = ["un","iq","ue"]
출력: 4
설명: 모든 유효한 연결은 다음과 같습니다.
- ""
- "un"
- "iq"
- "ue"
- "uniq" ("un" + "iq")
- "ique" ("iq" + "ue")
최대 길이는 4입니다.

예시 2:

입력: arr = ["cha","r","act","ers"]
출력: 6
설명: 가능한 가장 긴 문자열은 "chaers" ("cha" + "ers") 와 "acters" ("act" + "ers").

예시 3:

입력: arr = ["abcdefghijklmnopqrstuvwxyz"]
출력: 26
설명: 유일한 문자열 arr에는 26자가 모두 있습니다.

조건:

• 1 <= arr.length <= 16
• 1 <= arr[i].length <= 26
• arr[i]영문 소문자만 포함합니다.

정답:

public class Solution {
    public int MaxLength(IList<string> arr) {
        
        string str = "";
        
        return BackTracking(arr, "", -1).Length;
    }
    
    private static string BackTracking(IList<string> arr, string str, int depth)
    {
        string strMemory = "";

        if (arr.Count - 1 == depth)
        {
            return str;
        }
        if ((str + arr[depth + 1]).ToCharArray().Distinct().ToArray().Length == (str + arr[depth + 1]).Length)
        {
            strMemory = BackTracking(arr, str + arr[depth + 1], depth + 1);
        }
        else
        {
            strMemory = BackTracking(arr, str, depth + 1);
        }

        string nextStr = BackTracking(arr, str, depth + 1);

        if (strMemory.Length < nextStr.Length)
        {
            return nextStr;
        }
        else
        {
            return strMemory;
        }
    }
}

해설: strMemory 변수에는 처음부터 풀었을때를 기억하고 nextStr에는 넘어갔을때를 기억해서 어디값이 더 긴지 비교 후 return해주었습니다.