Home › DSA › Company Practice

easy Buddy Strings

Problem Statement

Given two strings a and b, return true if they can be considered "buddy strings". Otherwise, return false.

Two strings are buddy strings if you can swap any two letters in one string to make it equal to the other string.

Examples

Example 1:
- Input: a = "xy", b = "yx"
- Expected Output: true
- Justification: Swapping 'x' and 'y' in string a results in "yx", which matches string b.
Example 2:
- Input: a = "ab", b = "cd"
- Expected Output: false
- Justification: There are differences at every position, and swapping any characters in a cannot make it equal to b.
Example 3:
- Input: a = "abcde", b = "acbde"
- Expected Output: true
- Justification: Swapping 'b' and 'c' in string a results in "acbde", which matches string b.

Try it yourself

Try solving this question here:

✅ Solution Buddy Strings

Problem Statement

Given two strings a and b, return true if they can be considered "buddy strings". Otherwise, return false.

Two strings are buddy strings if you can swap any two letters in one string to make it equal to the other string.

Examples

Example 1:
- Input: a = "xy", b = "yx"
- Expected Output: true
- Justification: Swapping 'x' and 'y' in string a results in "yx", which matches string b.
Example 2:
- Input: a = "ab", b = "cd"
- Expected Output: false
- Justification: There are differences at every position, and swapping any characters in a cannot make it equal to b.
Example 3:
- Input: a = "abcde", b = "acbde"
- Expected Output: true
- Justification: Swapping 'b' and 'c' in string a results in "acbde", which matches string b. So, both strings are buddy strings.

Solution

To solve this problem, we start by comparing the lengths of the two strings. If their lengths differ, they cannot be buddy strings. For strings of equal length, we track the positions where they differ. If there are no differences and the first string has at least one repeating character, it means a swap could occur within the string to make it its own buddy string. If there are exactly two differences, we check if swapping the characters at these positions in one string makes the two strings equal. This approach ensures we accurately identify buddy strings by addressing both scenarios where strings are initially equal or need a specific swap to become equal.

Our approach is effective because it minimizes the number of checks needed to determine if two strings are buddy strings. By first checking the length, then the positions of difference, and finally the conditions for being buddy strings, we efficiently narrow down the possibilities with minimal computational overhead. This method balances thoroughness with efficiency, making it suitable for a wide range of inputs.

Step-by-step Algorithm

Initial Length Check:
- If a.length is not equal to b.length, return false immediately, as strings of different lengths cannot be buddy strings.
Handle Identical Strings:
- If the strings a and b are identical, then for them to be buddy strings, there must be at least one character in a that appears more than once. Use a frequency count array or a set to check for repeating characters. If a repeat is found, return true.
Identify and Record Differences:
- If a and b are not identical, iterate through both strings simultaneously to compare characters at each position.
- Record the indices where a and b differ. Use two variables, first and second, initialized to -1, to store these indices.
- If more than two differences are found, return false as a swap cannot resolve more than two differences.
Check for Exactly Two Differences:
- After identifying the indices of differences, check if swapping the characters at these positions in a would make it equal to b. This means that the character at first index in a should match the character at second index in b and vice versa.
Final Verification:
- If the conditions in step 4 are satisfied, return true, indicating that the strings are buddy strings by a single swap.
- Otherwise, return false.

Algorithm Walkthrough

Consider the input a = "abcde", b = "acbde".

Initial Length Check:
- Both strings a and b are of the same length. This check passes, allowing us to proceed to the next step.
Handle Identical Strings:
- The strings a and b are not identical, so we move to the next step. There's no need to check for repeating characters since the strings differ.
Identify and Record Differences:
- As we iterate through both strings from the beginning, they match at the first position. At the second position, we encounter a difference ('b' in a vs 'c' in b), so we record first = 1.
- Continuing, we find another difference at the third position ('c' in a vs 'b' in b), so we record second = 2. The rest of the characters match in both strings.
- There are exactly two differences, and no more, which is what we need for a potential swap to make a and b equal.
Check for Exactly Two Differences:
- With first = 1 and second = 2, we check if swapping the characters at these positions in a would make it equal to b. Specifically, we're looking to see if after the swap, a[first] equals b[second] and a[second] equals b[first].
- Before the swap: a = "abcde", b = "acbde"
- After a hypothetical swap in a (swapping 'b' and 'c'): a would become "acbde".
- This swapped version of a matches b exactly.
Final Verification:
- Since swapping 'b' and 'c' in a makes it identical to b, the strings are buddy strings. Therefore, we return true.

Code

java

public class Solution {

  // Method to check if two strings are buddy strings
  public boolean buddyStrings(String a, String b) {
    // Check for length equality
    if (a.length() != b.length()) return false;

    // Handling identical strings
    if (a.equals(b)) {
      int[] count = new int[26]; // Frequency count for characters
      for (int i = 0; i < a.length(); i++) {
        count[a.charAt(i) - 'a']++;
        if (count[a.charAt(i) - 'a'] > 1) return true; // Found a repeating character
      }
      return false; // No repeating characters
    } else {
      // Identifying positions where characters differ
      int first = -1, second = -1;
      for (int i = 0; i < a.length(); i++) {
        if (a.charAt(i) != b.charAt(i)) {
          if (first == -1) first = i; // First difference
          else if (second == -1) second = i; // Second difference
          else return false; // More than two differences
        }
      }
      // Checking if swapping makes the strings equal
      return (
        second != -1 &&
        a.charAt(first) == b.charAt(second) &&
        a.charAt(second) == b.charAt(first)
      );
    }
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(solution.buddyStrings("xy", "yx")); // true
    System.out.println(solution.buddyStrings("ab", "cd")); // false
    System.out.println(solution.buddyStrings("abcde", "acbde")); // true
  }
}

Complexity Analysis

Time Complexity: where n is the length of the strings, as the algorithm iterates over the strings at most once.
Space Complexity: for checking differences and in the worst case when the strings are identical to store character frequencies. However, because the character set is limited (assuming ASCII), this can also be considered in practical scenarios where the alphabet size is fixed.

🤖 Don't fully get this? Learn it with Claude

Stuck on Buddy Strings? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Buddy Strings** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Buddy Strings** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Buddy Strings**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Buddy Strings**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Toeplitz Matrix Longest Common Prefix →