Kevin And Set Of Strings

Hard
0/120
Average time to solve is 55m
profile
Contributed by
3 upvotes
Asked in company
Facebook

Problem statement

Kevin has ‘N’ strings and he wants to make all of them equivalent by performing only two types of operations (given below).

 swapEven => Choose any two characters that have even indexes and swap them.

 swapOdd => Choose any two characters that have odd indexed and swap them.

You have to help Kevin in finding the number of distinct strings that are still present in the set after Kevin converts maximum possible strings into its equivalent strings.

Note : 
Kevin may or may not be able to make all the strings equivalent to each other.

He can perform operations any number of times (including 0).

Strings are only composed of lowercase English alphabets.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain a single integer ‘N’ where ‘N’ is the total number of strings in the given set.

Next ‘N’ lines contain ‘N’ strings each separated by a new line.
Output Format : 
For each test case, print the total number of strings that are not equivalent to any other string in the given set.

Output for every test case will be printed in a separate line.
Note : 
You don’t need to print anything; It has already been taken care of.
Constraints : 
1 <= T <= 50
1 <= N <= 100
0 <= |S| <= 100

Time limit: 1 sec
Sample Input 1 :
2
4
xbya
xyab
axby
xayb
2
abc
cba
Sample Output 1 :
3
1
Explanation For Sample Input 1 :
In the first test case, only the 4th string can be converted into the 1st string (or vice-versa) and So, after this conversion distinct strings present in the set are {“xbya”, “xyab”, and “axby”}.

In the second test case, both the strings are equivalent to each other. So, the distinct string in the set is only 1.
Sample Input 2 :
3
2
abc
acb
3
aaaa
aaaa
aaaa
4
abcd
bcde
cdef
defg
Sample Output 2 :
2
1
4
Hint

Iteratively check which strings cannot be converted into another string.

Approaches (2)
Brute Force

The basic idea is to use nested loops to find which strings are distinct in the set. 

 

For checking the equivalency of two strings, the idea is to find whether two strings have the similar number of characters (with their respective frequencies) at even indexes or not (same for odd indexes) because if any two strings have same characters at even or odd places then the characters can be swapped to form the exact similar strings.

 

For Example:

 

Let’s assume two strings, s1 = “abcdefghaab” and s2 = “cfgbahedaab”.

 

For s1,
Characters at even indexes are = ‘a’(1), ‘b’(1), ‘d’(1), ‘f’(1), and  ‘h’(1).
Characters at odd indexes are = ‘a’(2), ‘b’(1), ‘c’(1), ‘e’(1), and ‘g’(1).

 

 

For s2,
Characters at even indexes are =  ‘a’(1), ‘b’(1), ‘d’(1), ‘f’(1), and ‘h’(1).

Characters at odd indexes are = ‘a’(2), ‘b’(1), ‘c’(1), ‘e’(1), and ‘g’(1).

 

 

Here, both the strings s1 and s2 have similar characters (with their frequency count) at their even and odd indexes, therefore s1 is equivalent to s2.

 

We can use two vectors of size 26 (one for storing frequency corresponding character at even indexes and the other for odd indexes). Steps are as follows:

 

  • Iterate through the given set (say, iterator be ‘i’).
    • Create two vectors (say, “even1” and “odd1”) for storing frequency of characters for string at ‘i’. These vectors have size 26 and pre-initialised with 0’s at all the indexes.
    • Iterate through the string at ‘i’.
      • Increment the frequency of the particular character at its respective index (even or odd)
    • Iterate through the given set again but from ‘i’ + 1 with respect to the position of the iterator of the above loop (say, iterator be ‘j’).
      • Now, check if string at ‘i’ is equivalent to ‘j’ by storing the frequency of characters at their respective indexes.
      • Make two vectors named “even2” and “odd2” (similarly as done for string at ‘i’).
      • Store frequencies of characters (similarly as done for string at ‘i’).
      • Check if, “even1” and “even2” are the same and “odd1” and “odd2” are same then break the inner loop because string at ‘i’ is not distinct.
      • Else, Repeat the process for all the remaining strings in the given set.
    • If string at ‘i’ is not matched with any other string in the inner loop then increment the counter by 1 because it is a distinct string.
    • Repeat the process for all the strings in the given set.
  • Return the counter.
Time Complexity

O((N^2) * M), where ‘N’ is the total number of strings in the given set and ‘M’ is the length of the longest string in the given set.

 

Since we are using one nested loop on the given set and one more loop on all the particular strings (inside the second loop, which is on the given set), therefore time complexity is O(N * N * M) which is represented by O((N^2) *  M).

Space Complexity

O(1)

 

Since we are not using any space in terms of the number of strings in the given set or the length of a particular string.

 

We are only using vectors of size 26 which are said to be of constant space in complexity analysis and so, the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Kevin And Set Of Strings
Full screen
Console