Determine if Two Strings Are Close

Problem: Two strings are considered close if you can produce one from the other using the following operations:

• Operation 1: Swap any two existing characters.
• For example, abc -> cba
• Operation 2: Transform every occurrence of one existing character into another existing character, and do the same with the other character.
• For example, aacb -> bbca (all a's turn into b's, and all b's turn into a's)

You can use these operations on either string as many times as necessary. Given two strings, word1 and word2, return true if word1 and word2 are close, and false otherwise.

Example:

Input: word1 = "nis", word2 = "sni"
Output: true
Explanation: You can attain word2 from word1 in 2 operations.
Apply Operation 1: "nis" -> "sin"
Apply Operation 1: "sin" -> "sni"

Approach: Let's understand what these two operations are telling us:

Operation 1: Swap any two existing characters - It is allowing us to freely reorder the string that means the order of characters in string does not matter.

Operation 2: Transform every occurrence of one existing character into another existing character, and do the same with the other character - It is allowing us to freely reassign the letters' frequencies. That means we can transform one string to another if for each letter of word1, there is a letter in word2 with equal frequency. For example word1 = "aaab" can be transformed to word2 = "bbba" by just turning all 'a's in to 'b' and 'b's into a in word1 or word2.

With the above understanding, we can divide this problem into two subproblems:

1. Unique characters in word1 and word2 should be same.

2. For each letter of word1 'word1Char', there is a letter in word2 whose frequency is same as frequency of word1Char.

We can easily solve both subproblems using hashing.

   

Implementation in C#:

        public bool CloseStrings(string word1, string word2)

    {

        if (word1.Length != word2.Length)

        {

            return false;

        }

        int[] countWord1 = new int[26];

        int[] countWord2 = new int[26];

        for (int i = 0; i < word1.Length; ++i)

        {

            countWord1[word1[i] - 'a'] += 1;

            countWord2word2[i] - 'a'] += 1;

        }

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

        {

            if (countWord1[i] > 0 && countWord2[i] == 0 ||

                countWord2[i] > 0 && countWord1[i] == 0)

            {

                return false;

            }

        }

        Array.Sort(countWord1);

        Array.Sort(countWord2);

        return Enumerable.SequenceEqual(countWord1, countWord1);

    }

Complexity: O(n) as count array size is constant (26).