Problem statement: Get the maximum length of a concatenated string with unique characters

Problem description:

You are given an array of strings arr. A string s is formed by the concatenation of a subsequence of arr that has unique characters.

 

Return the maximum possible length of s.

 

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

 

Example 1:

Input: arr = ["un","iq","ue"]

Output: 4

Explanation: All the valid concatenations are:

- ""

- "un"

- "iq"

- "ue"

- "uniq" ("un" + "iq")

- "ique" ("iq" + "ue")

Maximum length is 4.

 

Example 2:

Input: arr = ["cha","r","act","ers"]

Output: 6

Explanation: Possible longest valid concatenations are "chaers" ("cha" + "ers") and "acters" ("act" + "ers").

 

Example 3:

Input: arr = ["abcdefghijklmnopqrstuvwxyz"]

Output: 26

Explanation: The only string in arr has all 26 characters.

 

Constraints:

1 <= arr.length <= 16

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

arr[i] contains only lowercase English letters.

 

Solution:

import java.util.*;

import java.lang.*;

import java.util.stream.Collectors;

 

class Solution {

    public int maxLength(List<String> arr) {

        var combinations = new ArrayList<List<String>>();

        getCombinations(arr, combinations);

        var selections = combinations.stream().map(x->toString(x)).select (x -> isValid(x)).collect(Collectors.toList());

        return selections.stream().mapToInt(x->x.length()).max().getAsInt();

    }

   

public static void getCombinations(List<String> arr, List<List<String>> combinations) {

      int N = arr.size();

      for (int i = 0; i < (int) Math.pow(2, N); i++) {

          List<String> combination = new ArrayList<String>();

          for (int j = 0; j < N; j++) {

              if ((i & (1 << j)) > 0) {

                combination.add(arr.get(j));

              }

          }

          List<String> copy = new ArrayList<String>(combination);

          combinations.add(copy);

      }

   }

 

public static String toString(List<String> words) {

    StringBuilder sb = new StringBuilder();

    foreach (var word : words){

        sb.append(word);

    }

    return sb.toString();

}

public static boolean isValid(String word){

    Map<Character, Integer> charMap = new HashMap<>();

     for (int i = 0; i< word.length(); i++){

        if (charMap.containsKey(Character.valueOf(word.charAt(j)))) {

           return false;

        }

        charMap.put(Character.valueOf(word.charAt(i)), 1);

     }

     return true;

}

 

}