Solution For Count Pairs Of Similar Strings

Problem Statement:

Given a list of strings words, write a function to count the number of pairs (i, j) where i < j and words[i] and words[j] are similar. Similarity is defined as having the same length and the same set of characters, but not necessarily in the same order: for example, “stressed” and “desserts” are similar.

Example:

Input: words = [“tangram”, “anagram”, “pikachu”, “back”, “kabab”] Output: 2
Explanation: There are 2 pairs of words that are similar:
– (words[0], words[1]) = (“tangram”, “anagram”)
– (words[3], words[4]) = (“back”, “kabab”)

Solution:

We are given a list of strings, and we need to count all the pairs of similar strings.

To solve this problem, we can use a hash table to store the set of characters in each string. Then, we can loop through all the pairs of strings and check if their sets of characters are the same.

Here’s the detailed approach to solve the problem:

1. Create a hash table where the key is the sorted set of characters in each string and the value is the number of occurrences of that set.

2. Loop through all the pairs of strings and check if their sets of characters are equal and not empty.

3. If the sets of characters are equal, add the count of occurrences of the set to the answer.

4. Return the final answer.

Here’s the Python implementation of the above approach:

def count_pairs_of_similar_strings(words):

freq = {}
for word in words:
    key = tuple(sorted(set(word)))
    freq[key] = freq.get(key, 0) + 1

ans = 0
for i in range(len(words)):
    for j in range(i + 1, len(words)):
        key1 = tuple(sorted(set(words[i])))
        key2 = tuple(sorted(set(words[j])))
        if key1 == key2 and key1:
            ans += freq[key1]

return ans

Testing the solution on the given example

print(count_pairs_of_similar_strings([“tangram”, “anagram”, “pikachu”, “back”, “kabab”]))

Output: 2

Time Complexity:
The time complexity of the solution is O(n^2 * m log m), where n is the length of the list and m is the maximum length of a string in the list. This is because we are using nested loops to loop through all pairs of strings, and then we are sorting the set of characters in each string, which takes O(m log m) time.

Space Complexity:
The space complexity of the solution is O(n * m) because we are storing the set of characters for each string in a hash table with a maximum size of n and a maximum length of m.

Step by Step Implementation For Count Pairs Of Similar Strings

public int countPairsOfSimilarStrings(String[] words) {
 
        // create a map to store the count of each word
        HashMap map = new HashMap<>();
 
        // add each word to the map with count 1
        for (String word : words) {
            map.put(word, 1);
        }
 
        // for each word, check if there is another word with same characters but different order
        int count = 0;
        for (String word : words) {
 
            // create a temp array to store the characters of the current word
            char[] temp = word.toCharArray();
 
            // sort the temp array
            Arrays.sort(temp);
 
            // create a new string from the temp array
            String newWord = new String(temp);
 
            // check if the new string is present in the map
            if (map.containsKey(newWord)) {
 
                // if present, then increase the count by 1
                count++;
 
                // remove the new string from the map so that it is not considered again
                map.remove(newWord);
            }
        }
 
        return count;
    }

def count_pairs_of_similar_strings(words): 

# initialize a set to keep track of unique words and a counter for the number of pairs of similar words 

unique_words = set() 
pairs = 0

# loop through the list of words 

for word in words: 

# if the word is not in the set, add it 

if word not in unique_words: 

unique_words.add(word) 

# otherwise, it's a duplicate so increment the counter 

else: 

pairs += 1

# return the number of pairs 

return pairs

var countPairs = function(words, i, j, memo) {
    // base case: if i and j are the same, then there's only one pair
    if (i === j) return 1;
    
    // if i and j have been seen before, then return the memoized value
    if (memo.hasOwnProperty([i, j])) return memo[[i, j]];
    
    // initialize our counter and set our default return value to 0
    let count = 0;
    
    // loop through the rest of the array
    for (let k = i + 1; k <= j; k++) {
        // if the ith element is equal to the kth element, then we have a pair
        if (words[i] === words[k]) {
            // increment our counter and recurse on the subarray
            count += 1 + countPairs(words, i + 1, k, memo);
        }
    }
    
    // memoize the result and return
    memo[[i, j]] = count;
    return count;
};

int countPairsOfSimilarStrings(vector& words, int n, int m) {
    int res = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (words[i].size() != words[j].size()) continue;
            int cnt = 0;
            for (int k = 0; k < m; ++k) {
                if (words[i][k] == words[j][k]) ++cnt;
            }
            if (cnt == m) ++res;
        }
    }
    return res;
}

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace ConsoleApplication1 
{ 
    class Program 
    { 
        static void Main(string[] args) 
        { 
            string[] words = new string[] { "mass", "as", "hero", "superhero" }; 
            int result = CountPairsOfSimilarStrings(words); 
            Console.WriteLine(result); 
            Console.ReadLine(); 
        } 

        // Function to count the number of pairs of similar strings 
        static int CountPairsOfSimilarStrings(string[] words) 
        { 
            int count = 0; // Variable to store the number of pairs 

            // Loop through all the strings in the array 
            for (int i = 0; i < words.Length; i++) 
            { 
                // Loop through all the strings again 
                // (We don't need to compare the string with itself) 
                for (int j = 0; j < words.Length; j++) 
                { 
                    // If the strings are not the same and they are similar 
                    if (i != j && IsSimilar(words[i], words[j])) 
                    { 
                        // Increment the count 
                        count++; 
                    } 
                } 
            } 

            // Return the number of pairs 
            return count; 
        } 

        // Function to check if two strings are similar 
        static bool IsSimilar(string str1, string str2) 
        { 
            // If the strings are of different length, they can't be similar 
            if (str1.Length != str2.Length) 
            { 
                return false; 
            } 

            // Variable to store the number of differences between the two strings 
            int diffCount = 0; 

            // Loop through all the characters in the strings 
            for (int i = 0; i < str1.Length; i++) 
            { 
                // If the characters are not the same, increment the diffCount 
                if (str1[i] != str2[i]) 
                { 
                    diffCount++; 
                } 
            } 

            // If the diffCount is more than 2, the strings are not similar 
            if (diffCount > 2) 
            { 
                return false; 
            } 

            // Otherwise, the strings are similar 
            return true; 
        } 
    } 
}