{x}
blog image

Buddy Strings

Given two strings s and goal, return true if you can swap two letters in s so the result is equal to goal, otherwise, return false.

Swapping letters is defined as taking two indices i and j (0-indexed) such that i != j and swapping the characters at s[i] and s[j].

  • For example, swapping at indices 0 and 2 in "abcd" results in "cbad".

 

Example 1:

Input: s = "ab", goal = "ba"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal.

Example 2:

Input: s = "ab", goal = "ab"
Output: false
Explanation: The only letters you can swap are s[0] = 'a' and s[1] = 'b', which results in "ba" != goal.

Example 3:

Input: s = "aa", goal = "aa"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'a' to get "aa", which is equal to goal.

 

Constraints:

  • 1 <= s.length, goal.length <= 2 * 104
  • s and goal consist of lowercase letters.

Solution Explanation for Buddy Strings

The problem asks whether two strings, s and goal, can become identical after swapping exactly two characters in s.

Approach:

The solution employs a clever approach that leverages character counts and the number of differing characters between the two strings. Here's a breakdown:

  1. Length Check: If the lengths of s and goal are different, it's impossible to make them identical by swapping characters, so we return false.

  2. Character Count Comparison: We use a Counter (or equivalent in other languages) to count the occurrences of each character in both strings. If the character counts are different, it implies that some characters are missing or extra in one string compared to the other. In this case, we cannot make them identical by swapping, and we return false.

  3. Difference Count: We count the number of positions where s[i] and goal[i] are different. Let's call this diff.

  4. Conditions for Success:

    • diff == 2: If diff is 2, it means exactly two characters need to be swapped to make the strings identical, so we return true.
    • diff == 0 and Repeated Characters: If diff is 0, it means the strings are already identical or could become identical by swapping identical characters (e.g., "aa" can become "aa" by swapping the 'a's). In this scenario, we check if either string has at least one character that appears more than once. If so, we return true because a swap of identical characters is possible; otherwise, we return false.

Time Complexity Analysis:

  • Character counting: O(n), where n is the length of the strings.
  • Difference counting: O(n)
  • Checking for repeated characters (if diff == 0): O(n) (in worst case, iterating through the entire character count array)

Therefore, the overall time complexity is O(n), linear in the length of the input strings.

Space Complexity Analysis:

The space complexity is O(1) because the space used by the character counters is constant (limited by the size of the alphabet, 26 for lowercase English letters). Note that the size of the alphabet is considered constant, not dependent on n.

Code Examples:

The provided code showcases the solution in multiple languages: Python, Java, C++, Go, and TypeScript. All implementations follow the same logic outlined above. They efficiently count characters, compare counts, and determine if a swap of two characters (or two identical characters) would make the strings equal.