Problem Statement in English

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

  • Choose two indices i and j i < j and j - i is even, then swap s1[i] and s1[j].

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

Approach

Since we can swap characters at even indices with each other and characters at odd indices with each other, we can sort the characters at even and odd indices separately for both strings and compare them.

If they are the same, then we can make s1 equal to s2, otherwise we cannot.

And we’re done!

Solution in Python


class Solution:
    def checkStrings(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 characters at even and odd indices separately.

  • Space: $O(n)$
    Since we store the characters at even and odd indices separately.

And we are done.