Check if Strings Can be Made Equal With Operations II

Check if Strings Can be Made Equal With Operations II

What is this problem about?

This is the "Medium" version of the previous problem. You are given two strings of equal length $n$, and you can swap characters at indices $i$ and $j$ if $j - i$ is even. This effectively means you can move any character at an even index to any other even index, and any character at an odd index to any other odd index.

Why is this asked in interviews?

This question tests your ability to generalize a pattern. It moves from the specific "length 4" case to an arbitrary length $n$. It evaluates whether you understand that the "even-index" and "odd-index" characters are two independent sets that never mix. This is a fundamental concept in parity and sorting.

Algorithmic pattern used

The pattern used is Hash Table Counting or Sorting based on Parity. You separate the characters of each string into two groups: those at even positions and those at odd positions. For the two strings to be transformable into each other, the multiset of even-position characters must be identical for both strings, and the same must be true for the odd-position characters.

Example explanation

$s1 = "abeac", s2 = "ecaba"$

• Even indices in $s1$ (0, 2, 4): {a, e, c}
• Even indices in $s2$ (0, 2, 4): {e, a, a} -> Mismatch! (s1 has 'c', s2 has an extra 'a'). Result: False. If $s1 = "abcd", s2 = "cdab"$:
• Even $s1$: {a, c}, Even $s2$: {c, a}. (Match)
• Odd $s1$: {b, d}, Odd $s2$: {d, b}. (Match) Result: True.

Common mistakes candidates make

A common mistake is trying to perform the swaps using a sorting algorithm, which is unnecessary. Another is failing to use a frequency map or sorting to compare the multisets efficiently, leading to $O(N^2)$ complexity instead of $O(N)$. Some candidates also forget that even/odd sets must be compared separately.

Interview preparation tip

Whenever a problem restricts swaps to a certain distance (like "swap if $|i-j|$ is even" or "swap if $|i-j|$ is a multiple of $k$"), realize that the array is split into $k$ independent groups. Elements can only move within their own group.