【Day54】1239. 串联字符串的最大长度

1239. 串联字符串的最大长度

给定一个字符串数组 arr,字符串 s 是将 arr 某一子序列字符串连接所得的字符串,如果 s 中的每一个字符都只出现过一次,那么它就是一个可行解。

请返回所有可行解 s 中最长长度。

示例 1:

输入:arr = ["un","iq","ue"]
输出:4
解释:所有可能的串联组合是 "","un","iq","ue","uniq" 和 "ique",最大长度为 4。

示例 2:

输入:arr = ["cha","r","act","ers"]
输出:6
解释:可能的解答有 "chaers" 和 "acters"。

示例 3:

输入:arr = ["abcdefghijklmnopqrstuvwxyz"]
输出:26

提示:

  • 1 <= arr.length <= 16
  • 1 <= arr[i].length <= 26
  • arr[i] 中只含有小写英文字母

题解:

class Solution {
public:
    int maxLength(vector &arr) {
        int ans = 0;
        vector masks = {0};
        for (string &s : arr) {
            int mask = 0;
            for (char ch : s) {
                ch -= 'a';
                if ((mask >> ch) & 1) { // 若 mask 已有 ch,则说明 s 含有重复字母,无法构成可行解
                    mask = 0;
                    break;
                }
                mask |= 1 << ch; // 将 ch 加入 mask 中
            }
            if (mask == 0) {
                continue;
            }
            int n = masks.size();
            for (int i = 0; i < n; ++i) {
                int m = masks[i];
                if ((m & mask) == 0) { // m 和 mask 无公共元素
                    masks.push_back(m | mask);
                    ans = max(ans, __builtin_popcount(m | mask));
                }
            }
        }
        return ans;
    }
};

   转载规则


《【Day54】1239. 串联字符串的最大长度》 Tyzhao 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
【Day55】1600.皇位继承顺序 【Day55】1600.皇位继承顺序
1600. 皇位继承顺序一个王国里住着国王、他的孩子们、他的孙子们等等。每一个时间点,这个家庭里有人出生也有人死亡。 这个王国有一个明确规定的皇位继承顺序,第一继承人总是国王自己。我们定义递归函数 Successor(x, curOrder
2021-06-20
下一篇 
【Day53】483. 最小好进制 【Day53】483. 最小好进制
483. 最小好进制对于给定的整数 n, 如果n的k(k>=2)进制数的所有数位全为1,则称 k(k>=2)是 n 的一个好进制。 以字符串的形式给出 n, 以字符串的形式返回 n 的最小好进制。 示例 1: 输入:"
2021-06-18
  目录