Buddy Strings

LeetCode 889 | Difficulty: Easy

Easy

Problem Description

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 * 10^4`

- `s` and `goal` consist of lowercase letters.

Topics: Hash Table, String

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

---

Solutions

Solution 1: C# (Best: 68 ms)

Metric	Value
Runtime	68 ms
Memory	38.7 MB
Date	2022-01-03

Solution

public class Solution {
    public bool BuddyStrings(string s, string goal) {
        if(s.Length != goal.Length) return false;
        
        List<int> indices = new List<int>();
    int[] freq = new int[26];
    for (int i = 0; i < s.Length; i++)
    {
        if (s[i] != goal[i])
        {
            indices.Add(i);
        }
    }
    if (indices.Count == 2)
    {
        int k = indices[0], l = indices[1];
        if (s[k] == goal[l] && goal[k] == s[l]) return true;
    }
    if(indices.Count == 0)
    {
        foreach (var c in s)
        {
            freq[c-'a']++;
            if(freq[c-'a'] == 2) return true;
        }
    }
    return false;
    }
}

---

Complexity Analysis

Approach	Time	Space
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Hash map gives O(1) lookup — think about what to use as key vs value.