Twin String

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.

Examples:

Input  : arr[] = {"abcd", "cbad", "bacd"}
Output : 2
The 2nd string can be converted to the 1st by swapping 
the first and third characters. So there are 2 distinct 
strings as the third string cannot be converted to the 
first.

Input  : arr[] = {"abc", "cba"}
Output : 1

Thoughts

Use two maps/dictionaries (int[# of alphabets (assume string only consists of alphabet literals only)]), one for the even index char and one for the odd index char. Encode the string such that it contains all the key-value pair from odd and even maps/dictionaries. Use set (C++: unordered_set <string> , Java: Hashset<String>) to hash distinct twin strings.

Code

// C++ program to count distinct strings with even odd swapping
// allowed.
#include<bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 26;

// 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;
}

// Driver code
int main()
{
    string input[] = {"abcd", "acbd", "adcb", "cdba",
                      "bcda", "badc"};
    int n = sizeof(input)/sizeof(input[0]);

    cout << countDistinct(input, n);
    return 0;
}

Special Thanks for GeeksforGeeks' detailed explanation of this problem.