Last Updated: 3 Feb, 2021
Distinct Strings With Odd and Even Swapping Allowed
Moderate
Asked in companies
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.
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.
Approaches
- 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.
- We can avoid sorting the strings by using a different approach for encoding.
- The idea is to generate the encoded string using the frequency of each character from ‘a’ to ‘z’ and the position (i.e. odd or even) at which they occur.
- Firstly, find the frequency of characters present at even index positions.
- Also, find the frequency of characters present at odd index positions.
- Now, using these frequencies we create the encoded string as follows, for every character from ‘a’ to ‘z’:
- Concatenate the encoded string by- Frequency of that character at even position, followed by a separator (say ‘-’), followed by frequency of that character at the odd position.
- For example: Let the string be “abacaaab”.
- The frequency of characters at even position is { a:1, b:2, c:1, d:0, ….., z:0 }
- The frequency of characters at odd position is { a:4, b:0, c:0, d:0, ….., z:0 }
- So, the encoded string will be: “1-4-2-0-1-0-0-0.......-0-0-”.
- Now, any two strings will be are same if there 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:
- Find the frequency of even and odd indexed characters and store them in hash table say, freqEven and freqOdd.
- Initially, the encoded string is empty.
- Iterate through the characters from ‘a’ to ‘z’:
- Let the current character be ch.
- Concatenate the encoded string with “freqEven[ch]-freqOdd[ch]-”.
- If the encoded string is not present in the hashtable, then add it to the hashtable.
- Return the number of strings present in the hashtable.