Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Swapping positions at an even distance preserves index parity. Within the even positions or within the odd positions, arbitrary rearrangements are possible. Therefore equality is reachable exactly when each parity class has the same character multiset in both strings.

Approach

Build separate character-frequency maps for even and odd indices of each string. Compare the two even maps and the two odd maps, returning true only when both pairs match. Counts are necessary because equal character sets alone would ignore multiplicities. Global anagram equality is not enough: a required character cannot move from an even position to an odd one.

class Solution:
    def checkStrings(self, s1: str, s2: str) -> bool:
        n = len(s1)
        e1, o1 = defaultdict(int), defaultdict(int)
        e2, o2 = defaultdict(int), defaultdict(int)

        for i in range(n):
            if i % 2 == 0:
                e1[s1[i]] += 1
                e2[s2[i]] += 1
            else:
                o1[s1[i]] += 1
                o2[s2[i]] += 1

        return e1 == e2 and o1 == o2

Complexity analysis

Let n be the string length and σ the number of distinct characters. Time: O(n). Auxiliary space: O(σ) (at most O(n)).