Buddy Strings

Easy
233.

Buddy Strings

Buddy Strings is an easy coding problem on strings and hash table, asked in Amazon, Google and Adobe interviews.

Given two strings s and goal, return true if you can swap exactly two characters of s — at two different positions — so that the result equals goal.

Example 1

Input
s = "ab", goal = "ba"
Output
true

Example 2

Input
s = "ab", goal = "ab"
Output
false
Explanation
Any swap changes the string, since every letter is distinct.

Example 3

Input
s = "aa", goal = "aa"
Output
true
Explanation
Swapping the two a's leaves the string unchanged.

Constraints

  • 1 <= s.length, goal.length <= 40
  • Both consist of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {string} goal
 * @return {boolean}
 */
var buddyStrings = function(s, goal) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Buddy Strings — Solution in Python, Java & C++

Buddy Strings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and Google.

Buddy Strings is an easy coding problem on strings and hash table, asked in Amazon, Google and Adobe interviews.

  • Difficulty: Easy
  • Topics: Strings, Hash Table
  • Asked at: Amazon, Google, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given two strings s and goal, return true if you can swap exactly two characters of s — at two different positions — so that the result equals goal.

Example 1

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

Example 2

Input: s = "ab", goal = "ab"
Output: false
Explanation: Any swap changes the string, since every letter is distinct.

Example 3

Input: s = "aa", goal = "aa"
Output: true
Explanation: Swapping the two a's leaves the string unchanged.

Constraints

  • 1 <= s.length, goal.length <= 40
  • Both consist of lowercase English letters.

Hints for Buddy Strings

  1. Hint 1

    Different lengths can never be buddies.

  2. Hint 2

    If the strings are already equal, the swap must be a no-op — which needs a repeated letter somewhere.

  3. Hint 3

    Otherwise there must be exactly two mismatched positions, and they must be each other's mirror image.

How to solve Buddy Strings

Three cases: different lengths → no; equal strings → a swap must be a no-op, which needs a repeated letter; otherwise exactly two mismatches that mirror each other.

Approach

  1. Return false if the lengths differ.
  2. If s == goal, return whether s has a duplicate character.
  3. Collect the mismatch indices; return true iff there are exactly two and s[i] == goal[j] and s[j] == goal[i].

Why it works

A swap changes at most two positions, so more than two mismatches is impossible; exactly two mismatches are fixable only if swapping them makes both match; and zero mismatches requires a swap of two equal letters.

Complexity

  • Time — O(n)
  • Space — O(n) for the mismatch list (O(1) with early exit)

Pitfalls

  • s == goal with all-distinct letters is false — "ab" cannot be swapped into itself.
  • One mismatch is always false.

Reference solution

Python

def buddyStrings(s: str, goal: str) -> bool:
    if len(s) != len(goal):
        return False
    if s == goal:
        return len(set(s)) < len(s)
    diff = [i for i in range(len(s)) if s[i] != goal[i]]
    return len(diff) == 2 and s[diff[0]] == goal[diff[1]] and s[diff[1]] == goal[diff[0]]

Java

public static boolean buddyStrings(String s, String goal) {
    if (s.length() != goal.length()) return false;
    if (s.equals(goal)) {
        Set<Character> seen = new HashSet<>();
        for (int i = 0; i < s.length(); i++) seen.add(s.charAt(i));
        return seen.size() < s.length();
    }
    List<Integer> diff = new ArrayList<>();
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) != goal.charAt(i)) diff.add(i);
    }
    return diff.size() == 2
        && s.charAt(diff.get(0)) == goal.charAt(diff.get(1))
        && s.charAt(diff.get(1)) == goal.charAt(diff.get(0));
}

C++

bool buddyStrings(string s, string goal) {
    if (s.size() != goal.size()) return false;
    if (s == goal) {
        unordered_set<char> seen(s.begin(), s.end());
        return seen.size() < s.size();
    }
    vector<int> diff;
    for (int i = 0; i < (int) s.size(); i++) {
        if (s[i] != goal[i]) diff.push_back(i);
    }
    return diff.size() == 2 && s[diff[0]] == goal[diff[1]] && s[diff[1]] == goal[diff[0]];
}

JavaScript

var buddyStrings = function(s, goal) {
    if (s.length !== goal.length) return false;
    if (s === goal) {
        const seen = new Set();
        for (let i = 0; i < s.length; i++) seen.add(s[i]);
        return seen.size < s.length;
    }
    const diff = [];
    for (let i = 0; i < s.length; i++) {
        if (s[i] !== goal[i]) diff.push(i);
    }
    return diff.length === 2 && s[diff[0]] === goal[diff[1]] && s[diff[1]] === goal[diff[0]];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets