Distinct Strings With Odd and Even Swapping Allowed

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
4 upvotes
Asked in companies
MicrosoftCerner Corporation

Problem statement

You are given an array of strings. Your task is to find the number of unique strings.

A string is considered unique if it cannot be formed from any other string, present in the array, even after applying the following operations any number of times and in any order:

1. Swapping two characters present at odd indices.

2. Swapping two characters present at even indices.

Note: 
Strings contain only lowercase English alphabets.
Example: 
Let the array of strings be [“abcd”, “cbad”, “bdac”, “adcb”]. From the given array, strings “abcd”, “cbad”, and “adcb” can be transformed into one another by applying the given operations. But “bdac” cannot be transformed into any other string. Hence, there are only 2 unique strings in the array.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The very first line of input contains an integer ‘T’ denoting the number of test cases. 

The first line of every test case contains an integer ‘N’ denoting the number of strings present in the array.

The second line of every test case contains ‘N’ space-separated strings, which are present in the array.
Output format: 
For each test case, the number of unique strings present in the array is printed.

Output for each test case is printed on a separate line.
Note: 
You do not need to print anything, it has already been taken care of. Just return the number of unique strings.
Constraints: 
1 <= T <= 10 
1 <= N <= 2000
1 <= Length of String <= 1000

Time Limit: 1 sec

Where  ‘T’ represents the number of test cases and ‘N’ represents the number of strings present in the array.
Sample Input 1:
2
4
abcd cbad bdac adcb
2
abc cba
Sample Output 1:
2
1
Explanation 1:
For the first test case refer to the example explained above.

For the second test case we have, array: [“abc”, “cba”] and N = 2. From the given array, strings “abc” and “cba” can be transformed into one another by applying the given operations. Hence, there is only 1 unique string in the array.
Sample Input 2:
2
4
coding ninja docgni ainjn
3
code good code
Sample Output 2:
2
2
Hint

Try to avoid sorting and find a better way to encode the strings.

Approaches (2)
Encoding String Using Sorting
  • The idea behind this approach is to encode every string using the even and odd index characters of the string.
  • For any given string, we split the string into two substrings, one with all the even indexed characters, say evenString and the other with all the odd indexed characters, say oddString.
  • In order to generate the encoded string, we sort both these strings and concatenate them to generate a new string, say encodedString.
  • Now, any two strings are same, if their encoded strings are same.
  • So, we keep track of all the distinct encoded strings, using a hash table.
  • The number of distinct encoded strings will give us the number of unique strings in the array.

Algorithm:

  • Create a hashtable, to store the distinct encoded strings.
  • For each string in the array:
    • Split the string into evenString and oddString.
    • Sort evenString and oddString.
    • encodedString = evenString.concatinate(oddString)
    • If encodedString is not present in the hashtable, then add it to the hashtable.
  • Return the number of strings present in the hashtable.
Time Complexity

O(N*M*logM), where N is the number of strings in the array and M is the length of the longest string.

 

We are iterating over the complete array which requires O(N) time. For every string in the array we split it into two substrings which require O(M) time. Sorting the two substrings requires O(M*logM) time. Also accessing the hashtable takes O(M) time. Hence, the overall time complexity is O(N * (M + M*logM + M)) = O(N*M*logM).

Space Complexity

O(N + M), where N is the number of strings in the array and M is the length of the longest string.

 

In the worst case, O(N) extra space is required by the hashtable. Also, O(M) space is required for storing the substrings and the encoded string. Hence, the overall space complexity is O(N + M). 

Code Solution
(100% EXP penalty)
Distinct Strings With Odd and Even Swapping Allowed
Full screen
Console