Can we Make Strings Same by Unlimited Number of Swaps?

You are given two strings s and t which both have length n. You can pick one character in s and another in t and swap them. Given you can make unlimited number of swaps, return whether it’s possible to make the two strings equal.

Example 1
Input
s = “ab”
t = “ba”
Output
true

Example 2
Input
s = “aa”
t = “aa”
Output
true

How do we Swap Characters and Make Both String Same?

We can use a hash map to count the frequencies of characters from both strings. The given two strings are of same length, thus with unlimited swaps, we can make both strings equal if each character has even number of occurences.

1
2
3
4
5
6
7
8
9
10
11
12
13

bool solve(string s, string t) {
    unordered_map<char, int> data;
    for (const auto &n: s) {
        data[n] ++;
    }
    for (const auto &n: t) {
        data[n] ++;
    }
    for (const auto &[a, b]: data) {
        if (b & 1) return false;
    }
    return true;
}

bool solve(string s, string t) {
    unordered_map<char, int> data;
    for (const auto &n: s) {
        data[n] ++;
    }
    for (const auto &n: t) {
        data[n] ++;
    }
    for (const auto &[a, b]: data) {
        if (b & 1) return false;
    }
    return true;
}

The time complexity is O(N) as we are going through two strings once. And the space requirement is also O(N) as are using a hash map to store the letters and their frequencies. N is the total length of both strings.

See also: Teaching Kids Programming – Swap Characters to Equalize Strings

–EOF (The Ultimate Computing & Technology Blog) —