# Solving Leetcode Interviews in Seconds with AI: Maximum Length of a Concatenated String with Unique Characters


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "1239" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> 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.  

	# Explanation
	Here's the solution:

*   **High-level approach:**
    *   Represent each string in `arr` as a bitmask, where each bit corresponds to a letter of the alphabet. This allows efficient checking for unique characters and concatenation conflicts.
    *   Use dynamic programming (or recursion with memoization, which is essentially the same thing in this context) to explore all possible subsequences of `arr`. The state of the DP will be the current index in `arr` and the current bitmask representing the characters used so far.
    *   At each step, we have two choices: either include the current string in the subsequence (if it's compatible with the current bitmask) or exclude it.

*   **Complexity:**
    *   Runtime: O(2<sup>n</sup> * m), where n is the length of `arr` and m is the average length of strings in `arr`.
    *   Storage: O(2<sup>n</sup>), to store the DP table (memoization).

	
	# Code
	```python
	def maxLength(arr: list[str]) -> int:
    """
    Finds the maximum possible length of a string formed by the concatenation of a subsequence of arr that has unique characters.
    """

    masks = []
    for s in arr:
        mask = 0
        valid = True
        for char in s:
            bit = ord(char) - ord('a')
            if (mask >> bit) & 1:
                valid = False
                break
            mask |= (1 << bit)
        if valid:
            masks.append(mask)

    memo = {}

    def solve(index, current_mask):
        if (index, current_mask) in memo:
            return memo[(index, current_mask)]

        if index == len(masks):
            return 0

        # Option 1: Exclude the current string
        max_len = solve(index + 1, current_mask)

        # Option 2: Include the current string (if possible)
        if (masks[index] & current_mask) == 0:
            max_len = max(max_len, bin(masks[index]).count('1') + solve(index + 1, current_mask | masks[index]))

        memo[(index, current_mask)] = max_len
        return max_len

    return solve(0, 0)
	```