Buddy Strings

EASY

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⁴
s and goal consist of lowercase letters.

Approaches

Checkout 2 different approaches to solve Buddy Strings. Click on different approaches to view the approach and algorithm in detail.

Brute Force by Generating All Swaps

This approach involves generating every possible string that can be formed by swapping exactly two characters in s and checking if any of these generated strings match goal. It is a straightforward, exhaustive search method.

Algorithm

1. First, check if the lengths of s and goal are different. If they are, return false as no swap can make them equal.
1. Use a nested loop to iterate through every unique pair of indices (i, j) in string s, where i < j.
1. For each pair, create a temporary copy of s as a character array.
1. Swap the characters at indices i and j in the temporary copy.
1. Convert the modified character array back to a string and compare it with goal.
1. If the new string is equal to goal, it means a single swap was sufficient. Return true.
1. If the loops complete without finding any such valid swap, it means it's impossible. Return false.

The brute-force method systematically tries every possible swap. It uses two nested loops to select two distinct indices, i and j, from the string s. For each pair of indices, it performs the swap on a temporary copy of the string (usually a character array for easy modification). After the swap, the modified array is converted back into a string and compared with the goal string. If a match is found, we've successfully found a way to make s equal to goal with one swap, and we can immediately return true.

This method implicitly handles all cases:

If s and goal differ by a swap (e.g., s="ab", goal="ba"), the loop will eventually find the correct i and j to make them equal.
If s and goal are the same and s has duplicates (e.g., s="aa", goal="aa"), swapping the duplicate characters will result in the same string, leading to a match.
If s and goal are the same but s has no duplicates (e.g., s="ab", goal="ab"), any swap will produce a different string, so no match will be found, and the function will correctly return false after checking all possibilities.

class Solution {
    public boolean buddyStrings(String s, String goal) {
        if (s.length() != goal.length()) {
            return false;
        }

        // This handles both cases: s != goal and s == goal
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j < s.length(); j++) {
                char[] sChars = s.toCharArray();
                // Swap characters
                char temp = sChars[i];
                sChars[i] = sChars[j];
                sChars[j] = temp;
                
                if (String.valueOf(sChars).equals(goal)) {
                    return true;
                }
            }
        }

        return false;
    }
}

Complexity Analysis

Time Complexity: O(N^3), where N is the length of the string. The nested loops give a factor of O(N^2). Inside the loop, converting the string to a `char[]` and then back to a `String` for comparison each take O(N) time, leading to an overall complexity of O(N^2 * N) = O(N^3).Space Complexity: O(N), where N is the length of the string. A new character array of size N is created in each iteration of the inner loop.

Pros and Cons

Pros:

Simple to understand and implement.
Correctly covers all cases without complex conditional logic.

Cons:

Extremely inefficient for larger strings.
Will likely cause a 'Time Limit Exceeded' error on most coding platforms for the given constraints.

Code Solutions

Checking out 3 solutions in different languages for Buddy Strings. Click on different languages to view the code.

class Solution {
public
  boolean buddyStrings(String s, String goal) {
    int m = s.length(), n = goal.length();
    if (m != n) {
      return false;
    }
    int diff = 0;
    int[] cnt1 = new int[26];
    int[] cnt2 = new int[26];
    for (int i = 0; i < n; ++i) {
      int a = s.charAt(i), b = goal.charAt(i);
      ++cnt1[a - 'a'];
      ++cnt2[b - 'a'];
      if (a != b) {
        ++diff;
      }
    }
    boolean f = false;
    for (int i = 0; i < 26; ++i) {
      if (cnt1[i] != cnt2[i]) {
        return false;
      }
      if (cnt1[i] > 1) {
        f = true;
      }
    }
    return diff == 2 || (diff == 0 && f);
  }
}

Video Solution

Watch the video walkthrough for Buddy Strings

Data Structures:

Hash TableString

Companies:

DoorDash |