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 Table String

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 * 10⁴
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.

1class Solution {2    public boolean buddyStrings(String s, String goal) {3        if (s.length() != goal.length()) {4            return false;5        }6 7        // This handles both cases: s != goal and s == goal8        for (int i = 0; i < s.length(); i++) {9            for (int j = i + 1; j < s.length(); j++) {10                char[] sChars = s.toCharArray();11                // Swap characters12                char temp = sChars[i];13                sChars[i] = sChars[j];14                sChars[j] = temp;15                16                if (String.valueOf(sChars).equals(goal)) {17                    return true;18                }19            }20        }21 22        return false;23    }24}

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.

This optimal approach solves the problem in a single pass by analyzing the properties of the strings. Instead of simulating swaps, it directly checks for the conditions that must be true for s and goal to be buddy strings. It efficiently handles the two main scenarios: when the strings are identical and when they are different.

Algorithm

1. First, check if the lengths of s and goal are not equal. If they aren't, return false.
1. Case 1: s and goal are identical.
- If s.equals(goal), a swap is only valid if we can swap two identical characters.
- To check this, iterate through s and use a HashSet or a frequency array to detect if there are any duplicate characters.
- If a duplicate character exists, return true. Otherwise, return false.
1. Case 2: s and goal are different.
- Create a list to store the indices where the characters of s and goal do not match.
- Iterate through the strings and add any mismatching index to the list.
- After the iteration, if the list of differences does not contain exactly two indices, return false.
- If the list contains exactly two indices, say i and j, check if the characters are swappable: s.charAt(i) == goal.charAt(j) and s.charAt(j) == goal.charAt(i).
- If this condition is met, return true. Otherwise, return false.

Walkthrough

This method is based on a logical analysis of the problem constraints. It avoids the costly process of generating and testing all possible swaps.

First, a basic check: if the strings don't have the same length, they can never be buddy strings, so we return false.

Next, we consider two distinct possibilities:

s and goal are the same string: If s.equals(goal), we can only return true if we can perform a swap on s that results in s itself. This is only possible if we swap two identical characters. Therefore, the problem reduces to checking if s has any duplicate characters. A HashSet is perfect for this: we iterate through s, adding characters to the set. If we try to add a character that's already in the set, we've found a duplicate, and we can return true.
s and goal are different strings: For a single swap in s to produce goal, the two strings must differ in exactly two positions. We can find these positions by iterating through both strings simultaneously and recording the indices where s.charAt(i) != goal.charAt(i). We store these indices in a list. If, after checking all characters, the number of differing indices is not exactly two, it's impossible to make them equal with one swap, so we return false. If there are exactly two differing indices, say i and j, we must perform one final check: the characters must be cross-matched. That is, s[i] must equal goal[j] and s[j] must equal goal[i]. If this holds, they are buddy strings; otherwise, they are not.

This approach covers all conditions in linear time.

1import java.util.ArrayList;2import java.util.HashSet;3import java.util.List;4import java.util.Set;5 6class Solution {7    public boolean buddyStrings(String s, String goal) {8        if (s.length() != goal.length()) {9            return false;10        }11 12        if (s.equals(goal)) {13            Set<Character> distinctChars = new HashSet<>();14            for (char c : s.toCharArray()) {15                if (!distinctChars.add(c)) {16                    // Found a duplicate character, we can swap them to get the same string17                    return true;18                }19            }20            // No duplicates found, any swap will change the string21            return false;22        } else {23            List<Integer> diff = new ArrayList<>();24            for (int i = 0; i < s.length(); i++) {25                if (s.charAt(i) != goal.charAt(i)) {26                    diff.add(i);27                }28            }29 30            // If there are exactly two differing positions and the characters are swapped31            return (diff.size() == 2 &&32                    s.charAt(diff.get(0)) == goal.charAt(diff.get(1)) &&33                    s.charAt(diff.get(1)) == goal.charAt(diff.get(0)));34        }35    }36}

Complexity

Time

O(N), where N is the length of the strings. The `s.equals(goal)` check takes O(N). Both subsequent cases involve a single loop through the string, which is also O(N). Therefore, the total time complexity is linear.

Space

O(1). The `HashSet` will store at most 26 characters (the size of the alphabet), which is constant. The list of differences will only be processed if its size is 2, also constant. Thus, the space usage does not scale with the input size N.

Trade-offs

Pros

Highly efficient with linear time complexity.
Optimal space complexity.
Passes for large inputs within time limits.

Cons

The logic is slightly more complex than the brute-force approach because it requires handling two separate cases.

Solutions

Solution

1class Solution {2public3  boolean buddyStrings(String s, String goal) {4    int m = s.length(), n = goal.length();5    if (m != n) {6      return false;7    }8    int diff = 0;9    int[] cnt1 = new int[26];10    int[] cnt2 = new int[26];11    for (int i = 0; i < n; ++i) {12      int a = s.charAt(i), b = goal.charAt(i);13      ++cnt1[a - 'a'];14      ++cnt2[b - 'a'];15      if (a != b) {16        ++diff;17      }18    }19    boolean f = false;20    for (int i = 0; i < 26; ++i) {21      if (cnt1[i] != cnt2[i]) {22        return false;23      }24      if (cnt1[i] > 1) {25        f = true;26      }27    }28    return diff == 2 || (diff == 0 && f);29  }30}

1class Solution:2    def buddyStrings(self, s: str, goal: str) -> bool: m, n = len(s), len(goal) if m != n: return False cnt1, cnt2 = Counter(s), Counter(goal) if cnt1 != cnt2: return False diff = sum(s[i] != goal[i] for i in range(n)) return diff == 2 or (diff == 0 and any(v > 1 for v in cnt1 . values()))

1class Solution {2public:3  bool buddyStrings(string s, string goal) {4    int m = s.size(), n = goal.size();5    if (m != n)6      return false;7    int diff = 0;8    vector<int> cnt1(26);9    vector<int> cnt2(26);10    for (int i = 0; i < n; ++i) {11      ++cnt1[s[i] - 'a'];12      ++cnt2[goal[i] - 'a'];13      if (s[i] != goal[i])14        ++diff;15    }16    bool f = false;17    for (int i = 0; i < 26; ++i) {18      if (cnt1[i] != cnt2[i])19        return false;20      if (cnt1[i] > 1)21        f = true;22    }23    return diff == 2 || (diff == 0 && f);24  }25};

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 problem