題目

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.

題目大意

給定一個字符串數組 arr，字符串 s 是將 arr 某一子序列字符串連接所得的字符串，如果 s 中的每一個字符都只出現過一次，那麼它就是一個可行解。請返回所有可行解 s 中最長長度。

解題思路

  • 每個字符串數組可以想象為 26 位的 0101 二進制串。出現的字符對應的位上標記為 1，沒有出現的字符對應的位上標記為 0 。如果一個字符串中包含重複的字符，那麼它所有 1 的個數一定不等於字符串的長度。如果 2 個字符串每個字母都只出現了一次，那麼它們倆對應的二進制串 mask 相互與運算的結果一定為 0 ，即 0，1 互補了。利用這個特點，深搜所有解，保存出最長可行解的長度即可。

參考代碼

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) { // 如果字符串本身帶有重複的字符，需要排除
			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
}