Problem Statement in English

You’re given two strings s1 and s2. You can perform the following operation on s1 any number of times:

  • Choose two indices i and j such that $abs(i - j) == 2$ and swap the characters at those indices.

Return true if you can make s1 equal to s2 using the above operation, and false otherwise.

Approach

Instead of actually performing the operations, we can just check if the odd indexed characters of s1 are the same as the odd indexed characters of s2 and if the even indexed characters of s1 are the same as the even indexed characters of s2.

If both conditions are satisfied, then we can make s1 equal to s2 using the above operation.

And we’re done!

Solution in Python


class Solution:
    def canBeEqual(self, s1: str, s2: str) -> bool:
        N1, N2 = len(s1), len(s2)

        if N1 != N2:
            return False

        odds1, odds2 = [], []
        evens1, evens2 = [], []

        for i in range(N1):
            if i % 2:
                odds1.append(s1[i])
                odds2.append(s2[i])
            else:
                evens1.append(s1[i])
                evens2.append(s2[i])

        odds1.sort()
        odds2.sort()
        evens1.sort()
        evens2.sort()

        if odds1 == odds2 and evens1 == evens2:
            return True

        return False

Complexity

  • Time: $O(N \log N)$
    Since we sort the odd and even indexed characters of both strings.

  • Space: $O(N)$
    Since we store the odd and even indexed characters of both strings.

And we are done.