Kevin And Set Of Strings

Posted: 17 Feb, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

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.
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
Approach 1

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.
Try Problem