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 <= 40Both consist of lowercase English letters.
Hints for Buddy Strings
Hint 1
Different lengths can never be buddies.
Hint 2
If the strings are already equal, the swap must be a no-op — which needs a repeated letter somewhere.
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
- Return
falseif the lengths differ. - If
s == goal, return whethershas a duplicate character. - Collect the mismatch indices; return
trueiff there are exactly two ands[i] == goal[j]ands[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 == goalwith all-distinct letters isfalse—"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