#859

Easy

LeetCode Problem Workspace

Buddy Strings

Determine if two strings can become equal by swapping exactly two letters using a hash table for character tracking.

Problem Statement

Given two strings s and goal, determine if it is possible to swap exactly two letters in s so that it becomes equal to goal. Swapping is defined as selecting two distinct indices i and j and exchanging s[i] with s[j].

Return true if such a swap can make s equal to goal, otherwise return false. For example, s = "ab" and goal = "ba" returns true because swapping the first and second letters of s results in goal.

Examples

Example 1

Input: s = "ab", goal = "ba"

Output: true

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

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

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 Approach

Check Lengths and Early Exit

If s and goal have different lengths, immediately return false because no swap can reconcile differing string lengths.

Track Mismatches with a Hash Table

Iterate through both strings simultaneously, record indices where characters differ. Use a hash table to track character counts to detect duplicates, which allow swaps in identical strings.

Evaluate Swap Conditions

Return true if there are exactly two mismatched positions and swapping them aligns s with goal. Also return true if strings are identical but contain at least one duplicate character, enabling a valid swap.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each string is traversed once and character counts are tracked. Space complexity is O(1) or O(26) since only lowercase letters are counted using a fixed-size hash table.

What Interviewers Usually Probe

Asks if swapping two letters is sufficient when s and goal are identical with duplicates.
Probes whether the candidate handles strings of different lengths correctly.
Wants reasoning behind using a hash table for character frequency versus simple mismatch tracking.

Common Pitfalls or Variants

Common pitfalls

Failing to check for duplicate characters when s equals goal, missing valid swap cases.
Assuming any two mismatches can be swapped without verifying order matches goal.
Overcomplicating with nested loops instead of linear scan plus hash table.

Follow-up variants

Allow swapping any number of letters and check if s can become goal using minimal swaps.
Determine the number of distinct swaps needed to convert s to goal instead of just verifying one.
Extend to uppercase and mixed-case strings, adjusting hash table or frequency array accordingly.

FAQ

What exactly defines a swap in the Buddy Strings problem?

A swap is defined as selecting two distinct indices i and j in s and exchanging s[i] with s[j].

Can Buddy Strings return true if the strings are identical?

Yes, but only if there is at least one character that occurs more than once, allowing a valid swap.

Why use a hash table instead of just comparing mismatched indices?

A hash table allows detection of duplicate characters efficiently, which is required when strings are identical.

What should be done if s and goal have different lengths?

Return false immediately because no single swap can reconcile differing string lengths.

Does the pattern 'Hash Table plus String' apply to all variations of Buddy Strings?

Yes, it is essential for counting character frequencies and evaluating swap conditions efficiently.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

class Solution:
    def buddyStrings(self, s: str, goal: str) -> bool:
        m, n = len(s), len(goal)
        if m != n:
            return False
        cnt1, cnt2 = Counter(s), Counter(goal)
        if cnt1 != cnt2:
            return False
        diff = sum(s[i] != goal[i] for i in range(n))
        return diff == 2 or (diff == 0 and any(v > 1 for v in cnt1.values()))

Continue Practicing