We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Length of a Concatenated String with Unique Characters

Number: 1360

Difficulty: Medium

Paid? No

Companies: Microsoft, Amazon, Adobe, Meta

Problem Description

Given an array of strings, the goal is to form the longest possible string by concatenating a subsequence of the given array such that all characters in the resulting string are unique. A subsequence is derived from the array by deleting some or no elements without changing the order of the remaining elements.

Key Insights

  • Preprocess each string to filter out those with duplicate characters as they cannot contribute to a unique set.
  • Use backtracking (or DFS) to explore all combinations of valid strings.
  • Represent each string as a bit mask to quickly check for character conflicts when concatenating strings.
  • Combine bit masks using bitwise operations; if two masks have no overlapping bits (i.e., bitwise AND equals zero), they can be concatenated.

Space and Time Complexity

Time Complexity: O(2^n * k) where n is the number of valid strings after preprocessing and k is the average length of the strings.
Space Complexity: O(n) for the recursion and storing the bit masks.

Solution

The approach starts by filtering out strings that contain duplicate characters and representing each valid string by a bit mask with each bit corresponding to a specific lowercase English letter. Then, using a DFS/backtracking strategy, we attempt to concatenate these valid strings one by one while ensuring that the concatenated string maintains unique characters. At each recursive call, we check if including a string violates the uniqueness condition by ensuring that the bit mask of the current combination and that of the candidate string do not overlap (i.e., their bitwise AND is zero). If they do not conflict, we combine the masks and update the maximum length observed.

Code Solutions

# Python implementation with line-by-line comments
class Solution:
    def maxLength(self, arr):
        # Preprocess: Convert each string into a bitmask representation if string has all unique characters
        def getBitMask(s):
            mask = 0
            for c in s:
                bit = 1 << (ord(c) - ord('a'))
                # If bit is already set, duplicate found, return None
                if mask & bit:
                    return None
                mask |= bit
            return mask
        
        masks = []
        lengths = []
        # Create lists for valid strings: their bit representation and length
        for s in arr:
            bitmask = getBitMask(s)
            if bitmask is not None:
                masks.append(bitmask)
                lengths.append(len(s))
        
        self.maxLen = 0
        
        # Backtracking DFS to try all combinations
        def dfs(index, currentMask, currentLength):
            # update maximum length found so far
            self.maxLen = max(self.maxLen, currentLength)
            # iterate over candidates starting from the provided index
            for i in range(index, len(masks)):
                # If current mask and candidate mask share any common bit, skip candidate
                if currentMask & masks[i] == 0:
                    dfs(i + 1, currentMask | masks[i], currentLength + lengths[i])
        
        dfs(0, 0, 0)
        return self.maxLen

# Example usage:
# sol = Solution()
# print(sol.maxLength(["un","iq","ue"]))
← Back to All Questions