1239. Maximum Length of a Concatenated String with Unique Characters

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.

Rust Solution

struct Solution;

impl Solution {
    fn max_length(arr: Vec<String>) -> i32 {
        let arr: Vec<u32> = arr
            .into_iter()
            .filter_map(|s| {
                let mut bitset = 0;
                for b in s.bytes() {
                    let bit = 1 << (b - b'a');
                    if bitset & bit != 0 {
                        return None;
                    } else {
                        bitset |= bit
                    }
                }
                Some(bitset)
            })
            .collect();
        let n = arr.len();
        let mut res = 0;
        Self::dfs(0, 0, &mut res, &arr, n);
        res as i32
    }

    fn dfs(start: usize, cur: u32, max: &mut u32, arr: &[u32], n: usize) {
        if start == n {
            *max = (*max).max(cur.count_ones());
        } else {
            if arr[start] & cur == 0 {
                Self::dfs(start + 1, cur | arr[start], max, arr, n);
            }
            Self::dfs(start + 1, cur, max, arr, n);
        }
    }
}

#[test]
fn test() {
    let arr = vec_string!["un", "iq", "ue"];
    let res = 4;
    assert_eq!(Solution::max_length(arr), res);
    let arr = vec_string!["cha", "r", "act", "ers"];
    let res = 6;
    assert_eq!(Solution::max_length(arr), res);
    let arr = vec_string!["abcdefghijklmnopqrstuvwxyz"];
    let res = 26;
    assert_eq!(Solution::max_length(arr), res);
}

Having problems with this solution? Click here to submit an issue on github.