Buddy Strings

The problem: Given two lowercase letter strings A and B, return true if you can swap two characters in A to make it equal to B, otherwise return false.

First Approach

Solve this directly from the definition. If swapping two characters in A makes it equal to B, then both strings must have the same character signature (same letters with same counts). There’s one edge case: when both strings are identical, A must contain duplicate letters to allow a valid swap.

Time complexity: O(n) Space complexity: O(1)

bool buddyStrings(string a, string b) {
    // Lengths must be equal and non-empty
    if (a.size() != b.size() || a.empty() || b.empty()) return false;

    bool repeat = false;
    int sign[26] = {0};
    // Build signature of string A
    for(auto s : a)
        ++sign[s-'a'];
    for(auto s : b) {
        // Check if A has duplicates
        if (sign[s-'a'] > 1) repeat = true;
        --sign[s-'a'];        
    }

    // Check if A and B have same character signature
    for(auto n : sign)
        if (n!=0) return false;

    // Signatures match, compare character by character
    int i,j;
    for(i=0;i<a.size() && a[i]==b[i];++i) {}
    if (i==a.size()) return repeat; // Strings equal, depends on A having duplicate chars

    // Strings differ, do one swap
    for(j=i+1;a[j]!=b[i];++j) {}
    swap(a[j], a[i]);

    // After swap, check if strings match
    for(;i<a.size() && a[i]==b[i];++i) {}

    return i==a.size();
}

Cleaner Way to Check Duplicates and Differences

Use unordered_set container to remove duplicates. Compare the container’s size() with the string length to detect duplicates.

bool buddyStrings(string A, string B) {
    // Same length
    int len_A = A.size(), len_B = B.size();
    if (len_A != len_B) return false;
        
    // Repeat: same string, A needs repeated char, like "aab" "aab"
    int numChar_A = unordered_set<char>(A.begin(), A.end()).size();
    // Handle duplicate case quickly
    if (A == B && numChar_A < len_B) return true;

    vector<int> index_diff;
                    
    for (int i = 0; i < len_A; i++) {
        // diff records only different indices, count cannot exceed 2
        if (A[i] != B[i]) index_diff.push_back(i);
        if (index_diff.size() > 2) return false;
    }
    // Different indices count is 2 and corresponding letters cross-equal meet requirements
    return index_diff.size() == 2 &&
           A[index_diff[0]] == B[index_diff[1]] &&
           A[index_diff[1]] == B[index_diff[0]];
}

Key Insights

unordered_set for quick deduplication
One pass through both strings to record different indices

#bucket #string #hashset

BST Iterator with Stack Traversal Candy Distribution Algorithm