1239. Maximum Length of a Concatenated String with Unique Characters #

Problem #

Given an array of strings arr. String s is a concatenation of a sub-sequence of arr which have unique characters.

Return the maximum possible length of s.

Example 1:

Input: arr = ["un","iq","ue"]
Output: 4
Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique".
Maximum length is 4.

Example 2:

Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible solutions are "chaers" and "acters".

Example 3:

Input: arr = ["abcdefghijklmnopqrstuvwxyz"]
Output: 26

Constraints:

• 1 <= arr.length <= 16
• 1 <= arr[i].length <= 26
• arr[i] contains only lower case English letters.

Problem Summary #

Given a string array arr, string s is the string obtained by concatenating strings from a subsequence of arr. If every character in s appears only once, then it is a feasible solution. Return the maximum length among all feasible solutions s.

Solution Approach #

• Each string array can be imagined as a 26-bit 0101 binary string. The bit corresponding to a character that appears is marked as 1, and the bit corresponding to a character that does not appear is marked as 0. If a string contains duplicate characters, then the number of its 1s must not equal the length of the string. If every letter in two strings appears only once, then the result of the bitwise AND operation between their corresponding binary string masks must be 0, meaning the 0s and 1s are complementary. Using this property, perform a depth-first search over all solutions and save the length of the longest feasible solution.

Code #

package leetcode

import (
	"math/bits"
)

func maxLength(arr []string) int {
	c, res := []uint32{}, 0
	for _, s := range arr {
		var mask uint32
		for _, c := range s {
			mask = mask | 1<<(c-'a')
		}
		if len(s) != bits.OnesCount32(mask) { // If the string itself contains duplicate characters, it needs to be excluded
			continue
		}
		c = append(c, mask)
	}
	dfs(c, 0, 0, &res)
	return res
}

func dfs(c []uint32, index int, mask uint32, res *int) {
	*res = max(*res, bits.OnesCount32(mask))
	for i := index; i < len(c); i++ {
		if mask&c[i] == 0 {
			dfs(c, i+1, mask|c[i], res)
		}
	}
	return
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}