Maximum Length of a Concatenated String with Unique Characters

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
9 upvotes
Asked in company
Microsoft

Problem statement

You are given an array of string ‘arr’ of size ‘N’. Your task is to find the maximum possible length of string, with unique characters formed by the concatenation of sub-sequences of ‘arr’.

For example: 
Consider ‘arr’ = [‘cha’, ‘r’, ‘act’, ‘ers’], the strings formed with unique characters, [‘cha’, ‘r’, ‘act’, ‘ers’, ‘char’, ‘ract’, ‘chaers’, ‘acters’]. The string with maximum length is ‘chaers’ and ‘acters’ with length 6. Hence the answer is 6.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
 The first line of input contains the integer ‘T’ representing the number of test cases.

The first line of each test case contains ‘N’ space-separated strings representing the element of the array.
Output Format: 
For each test case, print a single integer representing the maximum length of the string of unique characters formed by the concatenation of sub-sequences of the array ‘arr’.

Print a separate line for each test case
Constraints: 
1 <= T <= 10
1 <= N <= 26
1 <= |arr[i]| <= 26

arr[i] contains only lowercase letters.

Time Limit: 1 sec
Note: 
You do not need to print anything. It has already been taken care of. Just implement the function.
Sample Input 1:
2
cha r act ers
abcdefghijklmnopqrstuvwxyz
Sample Output 1:
6
26
Explanation:
For the first test case, arr = [‘cha’, ‘r’, ‘act’, ‘ers’], the strings formed with unique characters, [‘cha’, ‘r’, ‘act’, ‘ers’, ‘char’, ‘ract’, ‘chaers’, ‘acters’]. The string with maximum length is ‘chaers’ and ‘acters’ with length 6. Hence the answer is 6.

For the second test case, arr = [‘abcdefghijklmnopqrstuvwxyz’], there is only one string in the array, and the string contains unique characters. The length of the string is 26. Hence the answer is 26.
Sample Input 2:
2
abc def f
yy bkhwmpbiisbldzknpm
Sample Output 2:
6   
0
Hint

Try all configurations of the strings.

Approaches (2)
Using Recursion

In this approach, we will try all the configurations of the string by using a set and applying DFS on the strings array. We will find the path, i.e., the length of the longest string of unique characters till the current position of the array, at any position.

  • We will check if the string has unique characters. If not, we will  return 0
  • Otherwise, add the current string from the next position of the current string with every other string and apply dfs on the resulting string.
  •  

We create dfs(strings, currString, position), where strings are the array of strings given, currString is the current string to be checked, the position is the position of the currString in the given array.

 

Algorithm:

  • Dfs(strings, currString, position) function
    • Initialise an empty set st
    • Iterate ch over currString
      • Insert ch in st
    • If the size of st is not equal to the length of currString
      • Return 0
    • Set res as the length of currString
    • Iterate currPos from position to the length of strings - 1
      • Set string as strings[currPos]
      • Set res as the maximum of res and dfs(strings, str + currString, currPos)
    • Return str
  • Set string as an empty string.
  • Return Dfs(arr, string, 0)
Time Complexity

O(2^N), where N is the number of strings in the array
 

We are iterating through every combination of strings. There are a total of 2^N combinations. Hence the overall time complexity is O(2^N).

Space Complexity

O(N), where N is the number of strings in the array.

 

In the worst case, the recursion stack will take a total O(N) space. Hence the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Maximum Length of a Concatenated String with Unique Characters
Full screen
Console