Check if Strings Can be Made Equal With Operations II

Problem

We are given two strings s1 and s2 of the same length.

We may perform this operation any number of times on either string:

• choose indices i < j
• require that j - i is even
• swap s[i] and s[j]

We need to determine whether s1 can be transformed into s2.

Key Insight

If j - i is even, then i and j have the same parity.

That means:

• a character at an even index can only move to another even index
• a character at an odd index can only move to another odd index

So the actual order inside even positions does not matter, and the actual order inside odd positions does not matter.

What matters is only this:

• the multiset of characters at even indices in s1 must match the multiset of characters at even indices in s2
• the multiset of characters at odd indices in s1 must match the multiset of characters at odd indices in s2

Once that is true, we can rearrange characters within each parity bucket using swaps.

Why This Works

This problem is not really about simulating swaps.

It is about understanding what the swap operation allows.

Because we can swap any two indices with the same parity:

• all even positions form one connected group
• all odd positions form another connected group

So within the even group, we can permute characters however we want. And within the odd group, we can also permute characters however we want.

That reduces the whole question to a frequency comparison.

Approach

We keep four frequency arrays:

• even-index counts for s1
• odd-index counts for s1
• even-index counts for s2
• odd-index counts for s2

Then:

1. Count characters at even positions in both strings
2. Count characters at odd positions in both strings
3. Compare the even buckets
4. Compare the odd buckets

If both match, return true. Otherwise return false.

Full Java Solution

import java.util.Arrays;

class Solution {
  public boolean checkStrings(String s1, String s2) {
    int[] odd1 = new int[26];
    int[] even1 = new int[26];
    int[] odd2 = new int[26];
    int[] even2 = new int[26];

    int n = s1.length();

    for (int i = 0; i < n; i = i + 2) {
      odd1[s1.charAt(i) - 'a']++;
    }
    for (int i = 1; i < n; i = i + 2) {
      even1[s1.charAt(i) - 'a']++;
    }
    for (int i = 0; i < n; i = i + 2) {
      odd2[s2.charAt(i) - 'a']++;
    }
    for (int i = 1; i < n; i = i + 2) {
      even2[s2.charAt(i) - 'a']++;
    }

    return Arrays.equals(even1, even2) && Arrays.equals(odd1, odd2);
  }
}

Small Note On Naming

In the code above, the arrays named odd are counting indices 0, 2, 4..., and the arrays named even are counting indices 1, 3, 5....

So the naming is flipped relative to zero-based indexing, but the logic is still completely correct because both strings are counted the same way.

Walkthrough

Take:

s1 = "abcdba"
s2 = "cabdab"

Even indices in zero-based indexing are 0, 2, 4.

For s1

• even positions: a, c, b
• odd positions: b, d, a

For s2

• even positions: c, b, a
• odd positions: a, d, b

The even-position multisets match. The odd-position multisets also match.

So the answer is true.

Complexity Analysis

Time Complexity: O(n)

• we scan the strings a constant number of times
• comparing the 26-sized arrays is O(1)

Space Complexity: O(1)

• only four arrays of size 26 are used

Common Mistakes

1. Trying to simulate swaps

That makes the problem look much harder than it is.

We do not need to build the actual transformed string. We only need to check whether the needed rearrangement is possible.

2. Ignoring parity

The entire problem depends on the fact that an allowed swap preserves parity.

If a character starts in an even index, it can never move to an odd index.

3. Sorting the whole string

That is not enough.

Two strings can have the same overall characters and still be impossible to transform if the parity buckets differ.

Why I Like This Problem

This is one of those problems where the implementation is short, but only after the right observation clicks.

At first it feels like a swap simulation problem. But after noticing that parity never changes, it becomes a clean counting question.

That kind of reduction is always satisfying.

Related Problems

• Check if Strings Can be Made Equal With Operations I — Easy
• Determine if Two Strings Are Close — Medium
• Valid Anagram — Easy