By Expert Funda Monday, March 30, 2026

LeetCode 2840 – Check if Strings Can be Made Equal With Operations II | ExpertFunda
Home› LeetCode› String Problems› LeetCode 2840
# 2840 · LeetCode

Check if Strings Can be Made Equal
With Operations II

Medium String Hash Map Sorting
TimeO(n)
SpaceO(1)
Acceptance~62%
LanguageJava
⚠️
Common trap: Many solutions compare mirror-index pairs (i, n-1-i) — that's LeetCode 2839 (Operations I). This problem allows swapping any two indices i, j where j − i is even, which is a fundamentally different (and simpler) rule.
📋

Problem Statement

You are given two strings s1 and s2, both of length n. An operation consists of choosing any two indices i and j such that i < j and j − i is even, then swapping s1[i] and s1[j].

You may perform this operation any number of times. Return true if you can make s1 equal to s2, otherwise return false.

Example 1 — Output: true
Input s1"abcdba"
Input s2"cabdab"
ExplanationEven-idx pools match, odd-idx pools match → true
Example 2 — Output: false
Input s1"abcd"
Input s2"cdba"
Explanations1 even pool {a,c} ≠ s2 even pool {c,b} → false
📌
Constraint: 1 ≤ n ≤ 10⁵, strings consist of lowercase English letters only.
💡

Intuition & Key Insight

The rule j − i is even means only indices of the same parity can be swapped. Think about why: if both i and j are even, their difference is even. If both are odd, their difference is also even. You can never swap an even index with an odd index.

This divides the string into two independent pools:

  • Even pool — characters at indices 0, 2, 4, … can be freely rearranged among themselves.
  • Odd pool — characters at indices 1, 3, 5, … can be freely rearranged among themselves.
✅
The check reduces to: Do s1 and s2 have identical character frequencies at even positions? And identical frequencies at odd positions? If yes → true.

Here is the parity split for the test case s1="abcdba", s2="cabdab":

s1 — even indices (amber) vs odd indices (blue)
ai=0
bi=1
ci=2
di=3
bi=4
ai=5
Even pool s1: {a, c, b}  ·  Odd pool s1: {b, d, a}
s2 — same parity split
ci=0
ai=1
bi=2
di=3
ai=4
bi=5
Even pool s2: {c, b, a}  ·  Odd pool s2: {a, d, b}
Sorted even: [a,b,c] = [a,b,c] ✓    Sorted odd: [a,b,d] = [a,b,d] ✓  → return true
🔍

Step-by-Step Frequency Trace

We walk both strings together with a step of 2, incrementing for s1 and decrementing for s2. At the end every count must be zero.

Even parity pass (start = 0, step = 2)
Index i
s1[i] → freq++
s2[i] → freq--
Running state
0
freq['a']++ → 1
freq['c']-- → -1
a=1, c=-1
2
freq['c']++ → 0
freq['b']-- → -1
a=1, c=0, b=-1
4
freq['b']++ → 0
freq['a']-- → 0
all zeros ✓
Odd parity pass (start = 1, step = 2)
Index i
s1[i] → freq++
s2[i] → freq--
Running state
1
freq['b']++ → 1
freq['a']-- → -1
b=1, a=-1
3
freq['d']++ → 1
freq['d']-- → 0
b=1, a=-1, d=0
5
freq['a']++ → 0
freq['b']-- → 0
all zeros ✓
✅
Both passes cancelled to zero → return true
☕

Java Solution — O(n) / O(1)

Java 
import java.util.Arrays;

class Solution {
    public boolean checkStrings(String s1, String s2) {
        // Check even-indexed characters, then odd-indexed characters
        return check(s1, s2, 0) && check(s1, s2, 1);
    }

    private boolean check(String s1, String s2, int start) {
        int[] freq = new int[26];

        // Step by 2 so we stay on the same parity
        for (int i = start; i < s1.length(); i += 2) {
            freq[s1.charAt(i) - 'a']++;  // count up for s1
            freq[s2.charAt(i) - 'a']--;  // count down for s2
        }

        // Every frequency must cancel to zero
        for (int count : freq) {
            if (count != 0) return false;
        }
        return true;
    }
}
Time Complexity
O(n)
Space Complexity
O(1)
🔑
The int[26] array is always fixed-size regardless of n, so space is truly O(1). We do exactly one pass per parity group, giving O(n) total.
⚖️

Alternative Approaches

Approach Time Space Notes
Frequency array (optimal) O(n) O(1) Single pass, int[26] — best for interviews
Sort parity sub-arrays O(n log n) O(n) Extract even/odd chars, sort, compare. Clean but allocates
HashMap per parity O(n) O(n) Readable, but boxing/hashing overhead vs int[]
XOR trick (chars only) O(n) O(1) Necessary but not sufficient — XOR match ≠ multiset match
Brute-force simulation O(2^(n/2)) O(n) Correct but exponential — only for tiny inputs / testing
Sort-based variant (Java) — cleaner to read, suitable if n is small:
Java — sort variant 
class Solution {
    public boolean checkStrings(String s1, String s2) {
        return sortedParity(s1, 0).equals(sortedParity(s2, 0))
            && sortedParity(s1, 1).equals(sortedParity(s2, 1));
    }

    private String sortedParity(String s, int start) {
        char[] chars = new char[(s.length() - start + 1) / 2];
        for (int i = start, j = 0; i < s.length(); i += 2)
            chars[j++] = s.charAt(i);
        Arrays.sort(chars);
        return new String(chars);
    }
}
🚫

Common Mistakes to Avoid

❌
Mistake 1 — Mirror-pair comparison: Checking that {s1[i], s1[n-1-i]} equals {s2[i], s2[n-1-i]} is the solution to problem 2839, not 2840. The allowed swap set here is much larger.
❌
Mistake 2 — XOR equality check: s1_even_xor == s2_even_xor is a necessary but not sufficient condition. The strings "aab" and "bba" have the same XOR but different multisets at even positions.
⚠️
Edge case — odd length: The middle character (index n/2 for even n, or ⌊n/2⌋ for odd n) naturally ends up in the even pool. The algorithm handles it correctly with no special case needed.
⚠️
Don't over-engineer: You don't need a HashMap<Character, Integer>. The alphabet is fixed at 26 — an int[26] is O(1) space and cache-friendly.
Continue Reading →