Scale Engineer

Buddy Strings

Easy
#0813Time: 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: 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.1 company
Data structures
Hash TableString
Companies
DoorDash

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

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.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem