1239. Maximum Length of a Concatenated String with Unique Characters

Description

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.

Constraints

• 1 <= arr.length <= 16

• 1 <= arr[i].length <= 26

• arr[i] contains only lower case English letters.

Approach

Links

• Binarysearch

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    private int maxLen = 0;
    
    public int maxLength(List<String> words) {
        if(words != null && !words.isEmpty()) {
            dfs(words, 0, "");
        }
        return maxLen;
    }
    
    private void dfs(List<String> words, int index, String word) {
        if(index > words.size()) {
            return;
        }
        
        if(isUniqueCharsInStr(word)) {
            maxLen = Math.max(maxLen, word.length());
        } else {
            return;
        }
        
        for(int i = index; i < words.size(); i++) {
            dfs(words, i+1, word + words.get(i));
        }
    }
    
    private boolean isUniqueCharsInStr(String s) {
        if(s.length() < 2) {
            return true;
        }
        Set<Character> set = new HashSet();
        for(char ch: s.toCharArray()) {
            if(set.contains(ch)) {
                return false;
            }
            set.add(ch);
        }
        return true;
    }
}

Follow up