Skip to main content
Talentd

Buddy Strings - Solution & Explanation

EasyHash TableString8 min readAsked at: Amazon, Meta, DoorDash +2
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: You get two strings s and goal. The task is to determine whether swapping exactly two characters in s can make it equal to goal. The swap must involve two different indices, and only one swap is allowed.

Approach 1: Direct Comparison with Character Swapping (O(n) time, O(1) space)

Scan both strings and record the indices where characters differ. If more than two mismatches appear, the swap cannot fix the strings. When exactly two mismatches exist, verify that swapping those characters in s would match goal (i.e., s[i] == goal[j] and s[j] == goal[i]). A special case appears when the strings are already identical. In that case, a valid swap requires at least one duplicate character so the string remains unchanged after swapping identical letters.

This approach relies on simple iteration and constant memory. You compare characters position by position and keep at most two mismatch indices. The duplicate-character check can be done using a small set or frequency array. Because the algorithm performs a single pass through the strings, the time complexity is O(n) with O(1) extra space.

Approach 2: Character Frequency and Permutation Check (O(n) time, O(1) space)

Another way to reason about the problem is through character frequency and permutation validation. First ensure both strings have identical character counts using a frequency map or fixed-size array for letters. If the frequencies differ, no swap can make the strings equal. Next, count the number of positions where the characters differ. A valid buddy swap exists when there are exactly two mismatches forming a reversible pair.

This approach emphasizes verifying that both strings are permutations of each other before analyzing mismatches. The frequency structure is typically implemented with a hash map or array, making it a natural application of hash table techniques combined with linear scans of a string. Like the first method, it runs in O(n) time and uses O(1) extra space because the alphabet size is fixed.

Recommended for interviews: The direct comparison method is usually the expected solution. Interviewers want to see that you detect mismatched indices and reason about the exact swap condition. Mentioning the identical-string edge case (requiring duplicate characters) shows strong attention to detail. The frequency-based method also works, but the mismatch comparison demonstrates clearer reasoning about the swap constraint.

Approach 1: Direct Comparison with Character Swapping

This approach involves a straightforward comparison between the two strings. First, check if both strings are equal in length. If not, return false immediately. Next, identify the indices where the two strings differ. If there are exactly two such indices and swapping these characters in the first string can make it identical to the second, return true. Additionally, handle the edge case where both strings are already identical but contain at least one character that repeats, in which case a swap is possible and returns true.

The function first checks if the strings are of different lengths, returning false immediately. It then handles the case when both strings are identical by checking for repeated characters using a set, since a swap is impossible without repetition. For differing strings, it constructs a list of differing positions. If there are exactly two differences and swapping them resolves equality, the function returns true.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n), as we traverse the strings with a single pass to gather differences.
Space Complexity: O(1) for constant-space operations, though storing differences requires space proportional to the number of differences.

Try this approach in the editor →

Approach 2: Character Frequency and Permutation Check

This alternative method relies on character frequency counts and permutation verifications. If the strings differ in length, they're immediately ruled out. By evaluating how character frequencies align and applying permutation checks, the function can discern valid swaps that potentially achieve the goal formation of the strings.

The Java Solution uses ArrayList to store differing indices while also handling special cases for direct equality and duplication presence. It'll iterate through the string, populating discrepancies only to check their viability for a simple swap.

Code

JavaC#

Java

C#

Complexity

Time Complexity: O(n), scanning all potential indices to locate and evaluate differences.
Space Complexity: O(n) theoretically with list storage though practically controlled by processing mechanism constraints.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Direct Comparison with Character Swapping

Time Complexity: O(n), as we traverse the strings with a single pass to gather differences.
Space Complexity: O(1) for constant-space operations, though storing differences requires space proportional to the number of differences.

Character Frequency and Permutation Check

Time Complexity: O(n), scanning all potential indices to locate and evaluate differences.
Space Complexity: O(n) theoretically with list storage though practically controlled by processing mechanism constraints.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Comparison with Character SwappingO(n)O(1)Best general solution. Quickly identifies mismatched indices and verifies swap conditions.
Character Frequency and Permutation CheckO(n)O(1)Useful when reasoning through permutation equality and validating character counts before mismatch checks.

Video Solution

Buddy Strings | GOOGLE | META | Leetcode-859 | Explanation ➕ Live Coding • codestorywithMIK • 13,487 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Buddy Strings easy or hard?
Buddy Strings is classified as an Easy problem on LeetCode. The main challenge is handling edge cases, especially when the two strings are already identical and require a duplicate character to allow a valid swap.
How to solve Buddy Strings in O(n)?
Traverse both strings and store positions where characters differ. If more than two mismatches appear, the answer is false. When exactly two mismatches exist, check if swapping those two characters in the first string matches the second. Handle the edge case where both strings are identical by verifying that a duplicate character exists.
What is the best approach for Buddy Strings?
The direct comparison approach is the most common solution. Iterate through both strings and record indices where characters differ. If there are exactly two mismatches and swapping those characters makes the strings equal, return true. This runs in O(n) time with O(1) extra space.
What data structure is used in Buddy Strings?
Most solutions use simple string traversal with optional help from a hash table or frequency array. A set or counting array helps detect duplicate characters when the strings are already identical.
What is the time complexity of Buddy Strings?
The optimal solution runs in O(n) time where n is the string length. You perform a single pass to detect mismatches or compute character frequencies. Space complexity is O(1) because only a few variables or a fixed-size frequency array are required.
Buddy Strings Python or Java solution approach?
Python or Java implementations typically iterate through the strings to track mismatch indices. Some versions also use a frequency array to confirm both strings contain the same characters. Both approaches achieve O(n) time complexity.
Is Buddy Strings asked at Google, Amazon, or Meta?
Buddy Strings appears in coding interview practice sets similar to those used by companies like Amazon and Google. The problem tests string manipulation, edge case handling, and basic hash or counting techniques, which are common interview topics.

Ready to solve this problem?

Practice Buddy Strings with our built-in code editor and test cases.

Practice on FleetCode
Previous

Check if One String Swap Can Make Strings Equal

Next

Determine if Two Strings Are Close