Teaching Kids Programming – Swap Characters to Equalize Strings

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given two lowercase alphabet strings s and t, both of them the same length. 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.

Constraints
n ≤ 100,000 where n is the length of s and t
Example 1
Input
s = “ab”
t = “ba”
Output
True
Example 2
Input
s = “aa”
t = “aa”
Output
True

Hints:
For both strings to be equal, all the characters in string S, and in string T must be equal. What does this tell us about their frequency ?

Swap Characters to Equalize Strings

We can do unlimited swaps, thus, we just have to check the frequencies for each character – needs to be even number. We can count on the concatenated strings:

1
2
3
4
5
6
7

class Solution:
    def solve(self, s, t):
        a = Counter(s + t)
        for i in a:
            if a[i] & 1:
                return False
        return True

class Solution:
    def solve(self, s, t):
        a = Counter(s + t)
        for i in a:
            if a[i] & 1:
                return False
        return True

Alternative, we can use the Counter.update:

1
2
3
4
5
6
7
8

class Solution:
    def solve(self, s, t):
        a = Counter(s)
        a.update(t)
        for i in a:
            if a[i] & 1:
                return False
        return True

class Solution:
    def solve(self, s, t):
        a = Counter(s)
        a.update(t)
        for i in a:
            if a[i] & 1:
                return False
        return True

Oneliner using all keyword:

1
2
3
4
5
6

class Solution:
    def solve(self, s, t):
        a = Counter(s)
        a.update(t)
        return all((a[i] & 1)==0 for i in a)
        # or: return all(i & 1 == 0 for i in a.values()) 

class Solution:
    def solve(self, s, t):
        a = Counter(s)
        a.update(t)
        return all((a[i] & 1)==0 for i in a)
        # or: return all(i & 1 == 0 for i in a.values()) 

If each character appears even number of times, we can perform exclusive-or and the result must be zero:

1
2
3
4
5
6
7
8

class Solution:
    def solve(self, s, t):
        x = 0
        for i in s: # or we can for i in s+t:
            x ^= ord(i)
        for i in t:
            x ^= ord(i)
        return x == 0

class Solution:
    def solve(self, s, t):
        x = 0
        for i in s: # or we can for i in s+t:
            x ^= ord(i)
        for i in t:
            x ^= ord(i)
        return x == 0

Fancy syntax using reduce:

1
2
3
4
5
6

class Solution:
    def solve(self, s, t):
        if s + t == "":
            return True
        x = reduce(lambda a, b: a ^ b, map(ord, list(s + t)))
        return x == 0

class Solution:
    def solve(self, s, t):
        if s + t == "":
            return True
        x = reduce(lambda a, b: a ^ b, map(ord, list(s + t)))
        return x == 0

Time complexity is O(S+T) and the space complexity is O(S+T) for approaches using Counter, or O(1) based on XOR.

See also: Can we Make Strings Same by Unlimited Number of Swaps?

–EOF (The Ultimate Computing & Technology Blog) —