Kevin And Set Of Strings

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.

The basic idea of this approach is to encode every string according to a given format and then check the number of distinct possible strings.

In the previous approach, we already know that if two strings having similar characters (with their corresponding frequencies) at even and odd places then these are equivalent to each other or we can say, we can convert one string to another by performing the given operations.

Format of encoding:

• Declare an empty string (say, “encode”).
• Declare two vectors (say, “even” and “odd”) to store frequencies of corresponding characters.
• Iterate through a particular string that you want to encode (iterator = ‘i’).
  • If, the index is even then increment the frequency of character at ‘i’ in the “even” vector at the corresponding place (for, ‘a’ it is 0). Similarly for characters at odd indexes.
• Iterate from 0 to 25 (for each character, iterator = ‘k’)
  • Insert the frequency of each character in the string “encode”. Always insert first the frequency when the character is at even index and then for odd index.
• Finally, you got your encoded string (“encode”).

Steps for complete approach:

• Make a HashSet to store the distinct encoded strings.
• Iterate through the given set (say, iterator be ‘i’).
  • Encode the string at ‘i’ and insert it into the HashSet.
• Return the size of HashSet.