မှတ်ချက် – ဒီ Post သည် Algorithm Interview Preparation အပိုင်းဆက်ဖြစ်သည်။

ကျနော်တို့ဒီနေ့ရှင်းမယ့် ပြဿနာက 1239. Maximum Length of a Concatenated String with Unique Characters ဆိုတဲ့ leetcode question ဘဲဖြစ်ပါတယ်။

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.

 

Example 1:

Input: arr = ["un","iq","ue"]
Output: 4
Explanation: All the valid concatenations are:
- ""
- "un"
- "iq"
- "ue"
- "uniq" ("un" + "iq")
- "ique" ("iq" + "ue")
Maximum length is 4.
Example 2:

Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible longest valid concatenations are "chaers" ("cha" + "ers") and "acters" ("act" + "ers").
Example 3:

Input: arr = ["abcdefghijklmnopqrstuvwxyz"]
Output: 26
Explanation: The only string in arr has all 26 characters.
 

Constraints:

1 <= arr.length <= 16
1 <= arr[i].length <= 26
arr[i] contains only lowercase English letters.

မေးခွန်းက strings တွေပါတဲ့ arr ဆိုတဲ့ array တခုပေးထားမယ်။ ကျနော်တို့က s ဆိုတဲ့ string တခုလုပ်ရမယ်၊ သူပေးထားတဲ့ arr ဆိုတဲ့ array ထဲက string တွေကို concat ဆက်ရမယ်၊ ဒါပေမယ့် s ထဲမှာပါတဲ့ စကားလုံးက unique ဖြစ်နေရမယ်။ နောက်ဆုံးလိုချင်တာကတော့မထပ်ဘဲနဲ့အရှည်ဆုံးလုပ်လို့ရတဲ့ string လိုချင်တာပေါ့။

သူဥပမာလေးတွေပေးထားတယ်။ ထားပါတော့ကျနော်တို့ကို ["un", "iq", "ue"] ဆိုတဲ့ array တခုပေးထားတယ်ထားပါတော့အဲ့ array ထဲမှာပါတဲ့ string တွေကိုမထပ်အောင်ဆတ်ကမယ်ဆိုရင် အောက်ကလိုရမယ်…

un
iq
ue
uniq ("un" + "iq")
ique ("iq" + "ue")

အဲ့တော့ string အရှည်ဆုံးက လေးခုဘဲရှိတယ်။ အဲ့တော့အဖြေက 4.

အဲ့တော့ဒီကောင်ကို approach လုပ်မယ်ဆိုရင်။ ပုံမှန်ကျနော်တို့စဥ်းစားတဲ့နည်းအတိုင်းဘဲ စဥ်းစားကြည့်မယ်ဆိုရင် ပထမဆုံး ကျနော်တို့ array[0] ရဲ့ value length ကိုယူမယ် နောက်ထက် string ကိုအခုလက်ရှိကောင်နဲ့စကားလုံးတလုံးချင်းစီတိုက်စစ်မယ်။ အဲ့ကောင် unique ဖြစ်နေတယ်ဆိုရင် ကျနော်တို့ array[0] string နဲ့ ပေါင်းလိုက်မယ်။

ကုဒ်ကိုတချက်ကြည့်လိုက်ကြရအောင်…

function maxLength(arr) {
    let maxLen = 0
    
    function backtrack(index, currentString) {
        // လက်ရှိ index နဲ့ arr ရဲ့ length တူနေတယ်ဆိုရင် base case ပေါ့
        if(index === arr.length) {
            maxLen = Math.max(maxLen, currentString.length);
            return;
        }

        // တကယ်လို့လက်ရှိ string က unique ဖြစ်နေတယ်ဆိုရင်
        // အဲ့ဒီ့ string ကိုပါ current string ထဲထည့်
        if (isUnique(currentString, arr[index])) {
            backtrack(index + 1, currentString + arr[index]);
        }


        // နောက် string စီကိုဆက်သွား
        backtrack(index + 1, currentString);

    }
    
    // လက်ရှိ string နဲ့ new string နဲ့တူလားစစ်ဖို့ 
    function isUnique(currentString, newString) {
        let charSet = new Set(currentString);
        for (let char of newString) {
            if (charSet.has(char)) {
                return false; // ထပ်နေတယ် charSet ထဲမှာရှိနေတယ်
            }
            charSet.add(char);
        }
        return true; // မထပ်နေဘူး 
    }

    backtrack(0, "");
    return maxLen;
}

Code overall တော့အထဲမှာလဲ comments တွေရေးထားတော့ ရှင်းမယ်ထင်ပါတယ်။ backtrack ဆိုတဲ့ function တခုရှိတယ်။ အဲ့ကောင်ကို recursive၊ သူ့ရဲ့ base case က index ကလက်ရှိ array ရဲ့ length နဲ့တူတယ်ဆိုရင် maxLen ကို return ပြန်လိုက်တယ်။

Time Complexity က O(2^n) ဖြစ်ပီးတော့ Space ကတော့ O(n) ဘဲဖြစ်ပါတယ်။