Distinct Strings With Odd and Even Swapping Allowed
You are given an array of strings. Your task is to find the number of unique strings.

A string is considered unique if it cannot be formed from any other string, present in the array, even after applying the following operations any number of times and in any order:

1. Swapping two characters present at odd indices.

2. Swapping two characters present at even indices.

Note:

Strings contain only lowercase English alphabets.

Example:

Let the array of strings be [“abcd”, “cbad”, “bdac”, “adcb”]. From the given array, strings “abcd”, “cbad”, and “adcb” can be transformed into one another by applying the given operations. But “bdac” cannot be transformed into any other string. Hence, there are only 2 unique strings in the array.

Input format:

The very first line of input contains an integer ‘T’ denoting the number of test cases. The first line of every test case contains an integer ‘N’ denoting the number of strings present in the array. The second line of every test case contains ‘N’ space-separated strings, which are present in the array.

Output format:

For each test case, the number of unique strings present in the array is printed. Output for each test case is printed on a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just return the number of unique strings.

Constraints:

1

Question

Distinct Strings With Odd and Even Swapping Allowed

You are given an array of strings. Your task is to find the number of unique strings.

A string is considered unique if it cannot be formed from any other string, present in the array, even after applying the following operations any number of times and in any order:

1. Swapping two characters present at odd indices.

2. Swapping two characters present at even indices.

Note:

Strings contain only lowercase English alphabets.

Example:

Let the array of strings be [“abcd”, “cbad”, “bdac”, “adcb”]. From the given array, strings “abcd”, “cbad”, and “adcb” can be transformed into one another by applying the given operations. But “bdac” cannot be transformed into any other string. Hence, there are only 2 unique strings in the array.

Input format:

The very first line of input contains an integer ‘T’ denoting the number of test cases. 

The first line of every test case contains an integer ‘N’ denoting the number of strings present in the array.

The second line of every test case contains ‘N’ space-separated strings, which are present in the array.

Output format:

For each test case, the number of unique strings present in the array is printed.

Output for each test case is printed on a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just return the number of unique strings.

Constraints:

1 <= T <= 10 
1 <= N <= 2000
1 <= Length of String <= 1000

Time Limit: 1 sec

Where  ‘T’ represents the number of test cases and ‘N’ represents the number of strings present in the array.

Accepted Answer

Encoding String Using Sorting

The idea behind this approach is to encode every string using the even and odd index characters of the string.
For any given string, we split the string into two substrings, one with all the even indexed characters, say evenString and the other with all the odd indexed characters, say oddString.
In order to generate the encoded string, we sort both these strings and concatenate them to generate a new string, say encodedString.
Now, any two strings are same, if their encoded strings are same.
So, we keep track of all the distinct encoded strings, using a hash table.
The number of distinct encoded strings will give us the number of unique strings in the array.

Algorithm:

Create a hashtable, to store the distinct encoded strings.
For each string in the array:
- Split the string into evenString and oddString.
- Sort evenString and oddString.
- encodedString = evenString.concatinate(oddString)
- If encodedString is not present in the hashtable, then add it to the hashtable.
Return the number of strings present in the hashtable.

Space Complexity: O(n)Explanation:

O(N + M), where N is the number of strings in the array and M is the length of the longest string.

In the worst case, O(N) extra space is required by the hashtable. Also, O(M) space is required for storing the substrings and the encoded string. Hence, the overall space complexity is O(N + M).

Time Complexity: O(n^2logn)Explanation:

O(N*M*logM), where N is the number of strings in the array and M is the length of the longest string.

We are iterating over the complete array which requires O(N) time. For every string in the array we split it into two substrings which require O(M) time. Sorting the two substrings requires O(M*logM) time. Also accessing the hashtable takes O(M) time. Hence, the overall time complexity is O(N * (M + M*logM + M)) = O(N*M*logM).

Java (SE 1.8)

/*
	Time complexity: O(N * M * logM)
	Space complexity: O(N + M)
	
	Where N is the number of Strings in the array,
	M is the length of the longest String.
*/

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Arrays;

public class Solution {
	// Method to sort a string alphabetically
	private static StringBuilder sortString(StringBuilder inputString) {
		// convert input string to char array
		char tempArray[] = inputString.toString().toCharArray();

		// sort tempArray
		Arrays.sort(tempArray);

		StringBuilder res = new StringBuilder();
		for (char c : tempArray) {
			res.append(c);
		}
		// return new sorted string
		return res;
	}

	public static String encodeString(String str) {
		StringBuilder evenString = new StringBuilder();
		StringBuilder oddString = new StringBuilder();

		// Generate subStrings from even and odd index characters.
		for (int i = 0; i < str.length(); i++) {
			if (i % 2 == 0) {
				evenString.append(str.charAt(i));
			} else {
				oddString.append(str.charAt(i));
			}
		}

		// Sort both the subStrings
		evenString = sortString(evenString);
		oddString = sortString(oddString);

		// Concatenate evenString and oddString to get the encoded String.
		StringBuilder encodedString = evenString.append(oddString);

		return encodedString.toString();
	}

	public static int countUniqueStrings(ArrayList arr) {
		// Hashtable to store the distinct encoded Strings.
		HashSet uniqueStrings = new HashSet();

		// Iterate through all the Strings.
		for (int i = 0; i < arr.size(); i++) {
			// Generate the encoded String.
			String encodedString = encodeString(arr.get(i));

			if (!uniqueStrings.contains(encodedString)) {
				// Encoded String has not been generated before. So, add it to the hashtable.
				uniqueStrings.add(encodedString);
			}
		}

		return uniqueStrings.size();
	}
}

Python (3.5)

'''
    Time complexity: O(N * M * logM)
	Space complexity: O(N + M)
	
	Where N is the number of strings in the array,
	M is the length of the longest string.
'''


def encodeString(str):
    evenString = ""
    oddString = ""

    # Generate substrings from even and odd index characters.
    for i in range(len(str)):
        if (i % 2 == 0):
            evenString += str[i]
        else:
            oddString += str[i]

    # Sort both the substrings
    evenString = ''.join(sorted(evenString))
    oddString = ''.join(sorted(oddString))

    # Concatenate evenString and oddString to get the encoded string.
    encodedString = ''.join([evenString, oddString])

    return encodedString


def countUniqueStrings(arr):
    # Hashtable to store the distinct encoded strings.
    uniqueStrings = set()

    # Iterate through all the strings.
    for i in range(len(arr)):
        # Generate the encoded string.
        encodedString = encodeString(arr[i])

        if (encodedString not in uniqueStrings):
            # Encoded string has not been generated before. So, add it to the hashtable.
            uniqueStrings.add(encodedString)

    return len(uniqueStrings)

C++ (g++ 5.4)

/*

	Time complexity: O(N * M * logM)

	Space complexity: O(N + M)

	

	Where N is the number of strings in the array,

	M is the length of the longest string.

*/



#include 

#include 



string encodeString(string &str)

{

	string evenString, oddString;



	// Generate substrings from even and odd index characters.

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

	{

		if (i % 2 == 0)

		{

			evenString.push_back(str[i]);

		}

		else

		{

			oddString.push_back(str[i]);

		}

	}



	// Sort both the substrings

	sort(evenString.begin(), evenString.end());

	sort(oddString.begin(), oddString.end());



	// Concatenate evenString and oddString to get the encoded string.

	string encodedString = evenString.append(oddString);



	return encodedString;

}



int countUniqueStrings(vector &arr)

{

	//  Hashtable to store the distinct encoded strings.

	unordered_set uniqueStrings;



	// Iterate through all the strings.

	for (int i = 0; i < arr.size(); i++)

	{

		// Generate the encoded string.

		string encodedString = encodeString(arr[i]);



		if (uniqueStrings.find(encodedString) == uniqueStrings.end())

		{

			// Encoded string has not been generated before. So, add it to the hashtable.

			uniqueStrings.insert(encodedString);

		}

	}



	return uniqueStrings.size();

}

Accepted Answer

Encoding String And Hashing

We can avoid sorting the strings by using a different approach for encoding.
The idea is to generate the encoded string using the frequency of each character from ‘a’ to ‘z’ and the position (i.e. odd or even) at which they occur.
Firstly, find the frequency of characters present at even index positions.
Also, find the frequency of characters present at odd index positions.
Now, using these frequencies we create the encoded string as follows, for every character from ‘a’ to ‘z’:
- Concatenate the encoded string by- Frequency of that character at even position, followed by a separator (say ‘-’), followed by frequency of that character at the odd position.
For example: Let the string be “abacaaab”.
- The frequency of characters at even position is { a:1, b:2, c:1, d:0, ….., z:0 }
- The frequency of characters at odd position is { a:4, b:0, c:0, d:0, ….., z:0 }
- So, the encoded string will be: “1-4-2-0-1-0-0-0.......-0-0-”.
Now, any two strings will be are same if there encoded strings are same.
So, we keep track of all the distinct encoded strings, using a hash table.
The number of distinct encoded strings will give us the number of unique strings in the array.

Algorithm:

Create a hashtable, to store the distinct encoded strings.
For each string in the array:
- Find the frequency of even and odd indexed characters and store them in hash table say, freqEven and freqOdd.
- Initially, the encoded string is empty.
- Iterate through the characters from ‘a’ to ‘z’:
  - Let the current character be ch.
  - Concatenate the encoded string with “freqEven[ch]-freqOdd[ch]-”.
- If the encoded string is not present in the hashtable, then add it to the hashtable.
Return the number of strings present in the hashtable.

Space Complexity: O(n)Explanation:

O(N), where N is the number of strings in the array.

In the worst case, O(N) extra space is required by the hashtable for storing distinct encoded strings. Also, approximately O(26*2*2) ~ O(1) space is required for storing the encoded string and O(26) ~ O(1) for the frequency hashtables. Hence, the overall space complexity is O(N).

Time Complexity: O(n^2)Explanation:

O(N*M), where N is the number of strings in the array and M is the length of the longest string.

We are iterating over the complete array which requires O(N) time. For every string in the array, we encode the string which requires O(M) time. Also accessing the hashtable takes O(M) time. Hence, the overall time complexity is O(N * (M + M)) = O(N*M).

Java (SE 1.8)

/*
	Time complexity: O(N * M)
	Space complexity: O(N)
	
	Where N is the number of Strings in the array,
	M is the length of the longest String.
*/

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Arrays;

public class Solution {

	public static String encodeString(String str) {
		int[] evenHash = new int[26];
		int[] oddHash = new int[26];

		for (int i = 0; i < 26; i++) {
			evenHash[i] = 0;
			oddHash[i] = 0;
		}

		// Store frequency of characters present even and odd index.
		for (int i = 0; i < str.length(); i++) {
			int pos = str.charAt(i) - 'a';
			if (i % 2 == 0) {
				++evenHash[pos];
			} else {
				++oddHash[pos];
			}
		}

		// Generate the encoded String.
		StringBuilder encodedString = new StringBuilder();

		for (int i = 0; i < 26; i++) {
			encodedString.append((char) (evenHash[i]));
			encodedString.append('-');

			encodedString.append((char) (oddHash[i]));
			encodedString.append('-');
		}

		return encodedString.toString();
	}

	public static int countUniqueStrings(ArrayList arr) {
		// Hashtable to store the distinct encoded Strings.
		HashSet uniqueStrings = new HashSet();

		// Iterate through all the Strings.
		for (int i = 0; i < arr.size(); i++) {
			// Generate the encoded String.
			String encodedString = encodeString(arr.get(i));

			if (!uniqueStrings.contains(encodedString)) {
				// Encoded String has not been generated before. So, add it to the hashtable.
				uniqueStrings.add(encodedString);
			}
		}

		return uniqueStrings.size();
	}
}

Python (3.5)

'''
    Time complexity: O(N * M)
	Space complexity: O(N)
	
	Where N is the number of strings in the array,
	M is the length of the longest string.
'''


def encodeString(s):
    evenHash = [0 for i in range(26)]
    oddHash = [0 for i in range(26)]

    # Store frequency of characters present even and odd index.
    for i in range(len(s)):
        pos = ord(s[i])-ord('a')
        if (i % 2 == 0):
            evenHash[pos] += 1
        else:
            oddHash[pos] += 1

    # Generate the encoded string.
    encodedString = ""
    for i in range(26):
        encodedString += str(evenHash[i])
        encodedString += '-'

        encodedString += str(oddHash[i])
        encodedString += '-'

    return encodedString


def countUniqueStrings(arr):
    # Hashtable to store the distinct encoded strings.
    uniqueStrings = set()

    # Iterate through all the strings.
    for i in range(len(arr)):
        # Generate the encoded string.
        encodedString = encodeString(arr[i])

        if (encodedString not in uniqueStrings):
            # Encoded string has not been generated before. So, add it to the hashtable.
            uniqueStrings.add(encodedString)

    return len(uniqueStrings)

C++ (g++ 5.4)

/*

	Time complexity: O(N * M)

	Space complexity: O(N)

	

	Where N is the number of strings in the array,

	M is the length of the longest string.

*/



#include 



string encodeString(string &str)

{

	vector evenHash(26, 0);

	vector oddHash(26, 0);



	// Store frequency of characters present even and odd index.

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

	{

		int pos = str[i] - 'a';

		if (i % 2 == 0)

		{

			++evenHash[pos];

		}

		else

		{

			++oddHash[pos];

		}

	}



	// Generate the encoded string.

	string encodedString = "";



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

	{

		encodedString.append(to_string(evenHash[i]));

		encodedString.push_back('-');



		encodedString.append(to_string(oddHash[i]));

		encodedString.push_back('-');

	}



	return encodedString;

}



int countUniqueStrings(vector &arr)

{

	//  Hashtable to store the distinct encoded strings.

	unordered_set uniqueStrings;



	// Iterate through all the strings.

	for (int i = 0; i < arr.size(); i++)

	{

		// Generate the encoded string.

		string encodedString = encodeString(arr[i]);



		if (uniqueStrings.find(encodedString) == uniqueStrings.end())

		{

			// Encoded string has not been generated before. So, add it to the hashtable.

			uniqueStrings.insert(encodedString);

		}

	}



	return uniqueStrings.size();

}

You are given an array of strings. Your task is to find the number of unique strings.

A string is considered unique if it cannot be formed from any other string, present in the array, even after applying the following operations any number of times and in any order:

1. Swapping two characters present at odd indices.

2. Swapping two characters present at even indices.

Note:

Example:

Input format:

Output format:

Note:

Constraints:

Popular interview questions of Full Stack Developer

Top HR questions asked in Tech Mahindra Full Stack Developer