Distinct strings with odd and even changes allowed - GeeksforGeeks

Distinct strings with odd and even changes allowed - GeeksforGeeks
Given an array of lower case strings, the task is to find the number of strings that are distinct. Two strings are distinct if on applying the following operations on one string the second string cannot be formed.

• A character on odd index can be swapped with another character at odd index only.
• A character on even index can be swapped with another character on even index only.

A simple solution is to run two loops. The outer loop picks a string and inner loop checks if there is a previously string which can be converted to current string by doing allowed transformations. This solution requires O(n2m) time where n is number of strings and m is maximum number of characters in any string.

An efficient solution generate an encoded string for every input string. The encoded has counts of even and odd positioned characters separated by a separator. Two strings are considered distinct if their encoded strings are same else not. Once we have a way to encode string, the problem reduces to counting distinct encoded strings. This is a typical problem of hashing. We create hash set and one by one store encodings of strings. If an encoding already exists, we ignore string. Else we store encoding in hash and increment count of distinct strings.

// Returns encoding of string that can be used for hashing.

// The idea is to return same encoding for strings which

// can become same after swapping a even positioned character

// with other even characters OR swapping an odd character

// with other odd characters.

string encodeString(string str)

{

    // hashEven stores the count of even indexed character

    // for each string hashOdd stores the count of odd

    // indexed characters for each string

    int hashEven[MAX_CHAR] = {0};

    int hashOdd[MAX_CHAR] = {0};

 

    // creating hash for each string

    for (int i=0; i<str.length(); i++)

    {

        char c = str[i];

        if (i&1) // If index of current character is odd

           hashOdd[c-'a']++;

        else

           hashEven[c-'a']++;

    }

 

    // For every character from 'a' to 'z', we store its

    // count at even position followed by a separator,

    // followed by count at odd position.

    string encoding = "";

    for (int i=0; i<MAX_CHAR; i++)

    {

       encoding += to_string(hashEven[i]);

       encoding += to_string('-');

       encoding += to_string(hashOdd[i]);

       encoding += to_string('-');

    }

    return encoding;

}

 

// This function basically uses a hashing based set to

// store strings which are distinct according to accoding

// to criteria given in question.

int countDistinct(string input[], int n)

{

    int countDist = 0;  // Initialize result

 

    // Create an empty set and store all distinct

    // strings in it.

    unordered_set<string> s;

    for (int i=0; i<n; i++)

    {

       // If this encoding appears first time, increment

       // count of distinct encodings.

       if (s.find(encodeString(input[i])) == s.end())

       {

           s.insert(encodeString(input[i]));

           countDist++;

       }

    }

 

    return countDist;

}

Read full article from Distinct strings with odd and even changes allowed - GeeksforGeeks