algoadvance

Leetcode 859. Buddy Strings

Problem Statement

Given two strings s and goal, return true if you can swap two letters in s such that the result is equal to goal. Otherwise, return false.

Clarifying Questions

1. What are the constraints on the input strings?
   • The lengths of s and goal will be between 1 and 2 * 10^4.
   • Both s and goal consist of lowercase letters.
2. Can we swap the same letter with itself?
   • Yes, swapping the same letter with itself is allowed, which counts as a “move.”
3. Can the strings be of different lengths?
   • No, if the lengths of s and goal are different, the result should be false.
4. What if the strings are already equal?
   • If the strings are equal, we need to check if there is at least one duplicate letter in s which allows a swap to still produce the same string.

Strategy

1. Length Check:
   • Immediately return false if the lengths of s and goal are different.
2. Equality Check:
   • If s is equal to goal, we need to check if there is at least one duplicate character in s which allows two positions to be swapped without changing the string.
3. Difference Position Collection:
   • If s is not equal to goal, we need to find all positions where the characters differ. For s to be convertible into goal by a single swap, there must be exactly two differing positions, and swapping these must result in goal.

Code

#include <vector>
#include <string>
#include <unordered_set>
using namespace std;

bool buddyStrings(string s, string goal) {
    // Step 1: Length check
    if (s.length() != goal.length()) return false;

    // Step 2: If the strings are equal, check for duplicates
    if (s == goal) {
        unordered_set<char> unique_chars;
        for (char c : s) {
            if (unique_chars.find(c) != unique_chars.end()) return true;
            unique_chars.insert(c);
        }
        return false;
    }

    // Step 3: Collect position differences
    vector<int> diff_positions;
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] != goal[i]) diff_positions.push_back(i);
    }

    // Step 4: Check if there are exactly two differences and valid swap can fix it
    return diff_positions.size() == 2 &&
           s[diff_positions[0]] == goal[diff_positions[1]] &&
           s[diff_positions[1]] == goal[diff_positions[0]];
}

Time Complexity

• Time Complexity: The function involves a single pass through the strings for various checks (i.e., character mismatch collection and duplicate character detection), which results in a time complexity of (O(n)), where (n) is the length of the string.
• Space Complexity: The space complexity is (O(1)) extra space for most parts except when using the unordered set for checking duplicates in the case where the strings are initially equal, resulting in (O(k)) where (k) is the number of unique characters. However, considering the number of possible characters (26), it is effectively (O(1)).

This strategy ensures that we efficiently determine if it’s possible to transform s into goal via a single swap.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?