Last Updated: 25 Aug, 2021

Maximum Length of a Concatenated String with Unique Characters

Moderate

Asked in company

Solve now

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.

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.

Solve now

Approaches

01 Approach

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)

Solve now

02 Approach

In this approach, we will try to make all configurations of the string by keeping the bitmask of the characters of the string in an integer, and we will set the initial string result as empty string-:

We will iterate over all the strings which do not have multiple characters.
For each string, we will if it conflicts with the combination found.
If the string has an intersection with the characters, we will skip the string.
In the end, we will return the combination of maximum length.

We will create a function countSetBits(bitSet), where bitSet is the integer whose set bits are counted.

Algorithm:

countSetBits(bitSet)
- Set count as 1
- While bitSet is not 0:
  - Add bitSet & 1 to count
  - Right shift bits in bitSet by 1
- Finally, return the count
Initialise an array bitArr with one value that is 0.
Set result as 0.
Iterate string through arr.
- Set bitSet as 0
- Iterate ch through string.
  - Set the bit at ch - ‘a’ position in bitSet
- Set n as the countSetBits(bitSet)
- If n is greater than the length of string
  - Then continue the loop.
- Iterate currBitSet through bitArr.
  - If (currBitSet & bitSet) is True
    - Then continue the loop
  - Otherwise, insert the (currSet | bitSet) in bitArr.
  - Set result as the maximum of countSetBits(currBitSet) + n and result
Finally, return the result

Solve now