medium Determine if Two Strings Are Close

Problem Statement:

Two strings are considered similar if you can make one string look like the other using the following two operations:

1. Swap any two characters.
   • For example, abde -> aedb (e and b swapped).
2. Replace every occurrence of one character with another, and replace the other character with the first one.
   • For example, acabbb -> bcbaaa (all a's turn into b's, and all b's turn into a's)

Given two strings, word1 and word2, return true if they can be made similar, otherwise return false.

Examples

Example 1:

• Input: word1 = "aacbbc", word2 = "bbcaca"
• Expected Output: true
• Justification: You can swap the 'a's and 'b's in word2 to make it "aacbcb", then swap the last two characters to match word1.

Example 2:

• Input: word1 = "xxyyzz", word2 = "zzxxyy"
• Expected Output: true
• Justification: Swapping characters 'x' with 'z' and then 'z' with 'y' in word2 will make it "xxyyzz", which matches word1.

Example 3:

• Input: word1 = "aabbcc", word2 = "aabbc"
• Expected Output: false
• Justification: The lengths of the two strings are different, so they can't be made to look the same.

Constraints:

• 1 <= word1.length, word2.length <= 10⁵
• word1 and word2 contain only lowercase English letters.

Solution

To solve this problem, the first step is to ensure that both strings have the same length. If they don't, they can't be made similar. Next, we need to check if both strings have the same set of characters. If one string has a character that the other doesn't, they can't be made to look the same. Lastly, we check the frequency of each character. Both strings must have the same frequency distribution of characters for them to be transformable into one another.

This approach is effective because it simplifies the problem into three main checks: length, character set, and frequency distribution. By ensuring these conditions, we can determine if one string can be transformed into the other using the allowed operations.

Step-by-step Algorithm:

1. Check Lengths:

   • If the lengths of word1 and word2 are not the same, return false because they cannot be transformed into each other.

2. Initialize Frequency Arrays and Character Sets:

   • Create two integer arrays, count1 and count2, each of size 26, to store the frequency of each character in word1 and word2 respectively.
   • Create two sets, set1 and set2, to store the unique characters present in word1 and word2 respectively.

3. Fill Frequency Arrays and Character Sets:

   • Iterate through each character in word1, update its corresponding frequency in count1, and add the character to set1.
   • Iterate through each character in word2, update its corresponding frequency in count2, and add the character to set2.

4. Sort Frequency Arrays:

   • Sort count1 and count2. Sorting helps to compare the character frequencies directly.

5. Compare Frequency Arrays and Character Sets:

   • Compare the sorted frequency arrays count1 and count2. If they are not the same, return false.
   • Compare the sets set1 and set2. If they are not the same, return false.

6. Return Result:

   • If both the sorted frequency arrays and the character sets are the same, return true.

Algorithm Walkthrough:

Let's walk through the algorithm using the example word1 = "aacbbc", word2 = "bbcaca".

1. Check Lengths:

   • Length of word1 is 6.
   • Length of word2 is 6.
   • Both lengths are the same, so proceed to the next step.

2. Initialize Frequency Arrays and Character Sets:

   • count1 = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
   • count2 = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
   • set1 = {}
   • set2 = {}

3. Fill Frequency Arrays and Character Sets:

   • For word1:
     • 'a': count1[0] becomes 1, set1 becomes {'a'}
     • 'a': count1[0] becomes 2, set1 remains {'a'}
     • 'c': count1[2] becomes 1, set1 becomes {'a', 'c'}
     • 'b': count1[1] becomes 1, set1 becomes {'a', 'b', 'c'}
     • 'b': count1[1] becomes 2, set1 remains {'a', 'b', 'c'}
     • 'c': count1[2] becomes 2, set1 remains {'a', 'b', 'c'}
   • For word2:
     • 'b': count2[1] becomes 1, set2 becomes {'b'}
     • 'b': count2[1] becomes 2, set2 remains {'b'}
     • 'c': count2[2] becomes 1, set2 becomes {'b', 'c'}
     • 'a': count2[0] becomes 1, set2 becomes {'a', 'b', 'c'}
     • 'c': count2[2] becomes 2, set2 remains {'a', 'b', 'c'}
     • 'a': count2[0] becomes 2, set2 remains {'a', 'b', 'c'}

4. Sort Frequency Arrays:

   • Sorted count1: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2]
   • Sorted count2: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2]

5. Compare Frequency Arrays and Character Sets:

   • count1 and count2 are equal after sorting.
   • set1 and set2 are equal.

6. Return Result:

   • Since both the sorted frequency arrays and character sets are the same, return true.

Code

import java.util.*;

public class Solution {

  public boolean closeStrings(String word1, String word2) {
    if (word1.length() != word2.length()) {
      return false; // The strings must be of equal length
    }

    int[] count1 = new int[26]; // Frequency of characters in word1
    int[] count2 = new int[26]; // Frequency of characters in word2
    Set<Character> set1 = new HashSet<>(); // Unique characters in word1
    Set<Character> set2 = new HashSet<>(); // Unique characters in word2

    for (char c : word1.toCharArray()) {
      count1[c - 'a']++;
      set1.add(c);
    }

    for (char c : word2.toCharArray()) {
      count2[c - 'a']++;
      set2.add(c);
    }

    Arrays.sort(count1); // Sort frequencies for comparison
    Arrays.sort(count2); // Sort frequencies for comparison

    return Arrays.equals(count1, count2) && set1.equals(set2);
  }

  public static void main(String[] args) {
    Solution sol = new Solution();

    // Example 1
    System.out.println(sol.closeStrings("aacbbc", "bbcaca")); // true

    // Example 2
    System.out.println(sol.closeStrings("xxyyzz", "zzxxyy")); // true

    // Example 3
    System.out.println(sol.closeStrings("aabbcc", "aabbc")); // false
  }
}

Complexity Analysis:

Time Complexity

The time complexity of this solution is where n is the length of the input strings. This is because we need to traverse the string. The sorting operation of count array takes constant time as its size is constant.

Space Complexity

The space complexity is because we are using fixed-size arrays (of size 26) and sets, and the extra space used does not depend on the input size.