LeetCode 2840 - Check if Strings Can be Made Equal With Operations II

The problem asks us to determine whether two strings s1 and s2 of equal length can be made identical using a specific type of swap operation.

leetcodemediumhash-tablestringsorting

LeetCode Problem 2840

Difficulty: 🟡 Medium
Topics: Hash Table, String, Sorting

Solution

Problem Understanding

The problem asks us to determine whether two strings s1 and s2 of equal length can be made identical using a specific type of swap operation. The operation allows us to choose any two indices i and j such that i < j and j - i is even, and then swap the characters at those positions. We can apply this operation any number of times on either string. The input strings consist only of lowercase English letters and can be up to 10^5 characters long, so we must find an efficient approach.

Restating, the problem essentially asks: Can we rearrange the characters in s1 and s2 such that, under the constraint that only characters at indices with the same parity (even-even or odd-odd) can swap, the two strings become identical?

Important observations include:

  1. Only indices of the same parity (even or odd) can interact through swaps. This implies that the characters at even indices in s1 can only move among even indices, and similarly for odd indices.
  2. If the multiset of characters at even indices in s1 does not match that of s2, or the same is true for odd indices, the strings cannot be made equal.
  3. Edge cases involve strings of length 1, strings where characters are repeated but unevenly distributed between odd and even indices, and already equal strings.

Approaches

Brute Force

A brute-force approach would try every valid swap combination on s1 and check if it ever equals s2. We could recursively generate all possible strings by performing swaps where j - i is even. While this guarantees correctness, it is extremely slow because the number of possible swaps grows combinatorially, leading to a time complexity far worse than O(n^2). For n up to 10^5, this is infeasible.

Optimal Approach

The key insight is that swaps only allow characters at even indices to rearrange among themselves and characters at odd indices among themselves. Therefore, the problem reduces to checking if the multiset of characters at even indices in s1 matches that in s2 and similarly for odd indices. If both match, then we can rearrange the characters within each parity group to make the strings identical.

This observation reduces the problem from simulating swaps to simply counting character frequencies at even and odd positions.

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n) Recursively try all valid swaps, infeasible for large n
Optimal O(n) O(1) Compare counts of characters at even and odd indices using fixed-size arrays or hash maps

Algorithm Walkthrough

  1. Initialize two counters for s1 representing characters at even indices and odd indices, and two counters for s2 similarly.
  2. Iterate over all indices of s1 and s2. For each index i, if i is even, increment the count of the character at that index in the even counter for the respective string; otherwise, increment the odd counter.
  3. After processing all characters, compare the even counters of s1 and s2. If they do not match, return false.
  4. Compare the odd counters of s1 and s2. If they do not match, return false.
  5. If both even and odd counters match, return true.

Why it works: The invariant here is that any sequence of valid swaps can only permute characters within the same parity group. Therefore, matching the character counts for each parity group guarantees that a sequence of swaps exists to transform s1 into s2.

Python Solution

from collections import Counter

class Solution:
    def checkStrings(self, s1: str, s2: str) -> bool:
        even_s1 = Counter()
        odd_s1 = Counter()
        even_s2 = Counter()
        odd_s2 = Counter()
        
        for i in range(len(s1)):
            if i % 2 == 0:
                even_s1[s1[i]] += 1
                even_s2[s2[i]] += 1
            else:
                odd_s1[s1[i]] += 1
                odd_s2[s2[i]] += 1
        
        return even_s1 == even_s2 and odd_s1 == odd_s2

The implementation first separates the characters into even and odd positions using two Counter objects for each string. Then it simply compares the counters. If they match for both parity groups, the strings can be made equal; otherwise, they cannot.

Go Solution

func checkStrings(s1 string, s2 string) bool {
    var evenS1, oddS1, evenS2, oddS2 [26]int

    for i := 0; i < len(s1); i++ {
        c1 := s1[i] - 'a'
        c2 := s2[i] - 'a'
        if i%2 == 0 {
            evenS1[c1]++
            evenS2[c2]++
        } else {
            oddS1[c1]++
            oddS2[c2]++
        }
    }

    for i := 0; i < 26; i++ {
        if evenS1[i] != evenS2[i] || oddS1[i] != oddS2[i] {
            return false
        }
    }
    return true
}

In Go, fixed-size arrays of length 26 are used for character counts, which is more efficient than a map for lowercase English letters. The logic remains the same: separate counts for even and odd positions, then compare.

Worked Examples

Example 1: s1 = "abcdba", s2 = "cabdab"

Index s1 Char s2 Char Even/Odd
0 a c Even
1 b a Odd
2 c b Even
3 d d Odd
4 b a Even
5 a b Odd

Even counters: s1 -> {a:1, c:1, b:1}, s2 -> {c:1, b:1, a:1} → match

Odd counters: s1 -> {b:1, d:1, a:1}, s2 -> {a:1, d:1, b:1} → match

Result: true

Example 2: s1 = "abe", s2 = "bea"

Even counters: s1 -> {a:1, e:1}, s2 -> {b:1, a:1} → do not match

Result: false

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass over the strings to count characters at even and odd indices
Space O(1) Counters or fixed-size arrays of length 26, independent of n

The time complexity is linear in the length of the string, and space is constant because the character set is limited to lowercase letters.

Test Cases

sol = Solution()

# Provided examples
assert sol.checkStrings("abcdba", "cabdab") == True  # able to swap to match
assert sol.checkStrings("abe", "bea") == False       # impossible

# Edge cases
assert sol.checkStrings("a", "a") == True            # single character, same
assert sol.checkStrings("a", "b") == False           # single character, different
assert sol.checkStrings("aa", "aa") == True          # two identical characters
assert sol.checkStrings("ab", "ba") == False         # two characters cannot swap, index diff not even
assert sol.checkStrings("abcabc", "cbacba") == True  # rearrangement possible within parity
assert sol.checkStrings("abcd", "dcba") == False     # cannot match with parity constraint
Test Why
"abcdba", "cabdab" Valid swaps allow strings to match
"abe", "bea" Impossible to match due to parity mismatch
"a", "a" Single character edge case, trivially true
"a", "b" Single character edge case, trivially false
"ab", "ba" Small string where index difference is odd, cannot swap
"abcabc", "cbacba" Multiple characters, parity swaps suffice
"abcd", "dcba" Cannot match due to parity constraints

Edge Cases

  1. Single-character strings: When n = 1, no swaps are possible. If the characters match, the result is true; otherwise false. Our implementation handles this automatically because even and odd counters are correctly incremented.
  2. Strings with only even or odd length mismatches: Strings where counts match globally but differ in parity groups. This could cause false positives in naive solutions that ignore parity. Our solution handles this by splitting counts by index parity.
  3. Repeated characters: Strings where characters are repeated but distributed differently across even and odd indices. This ensures that swaps cannot compensate for parity misalignment. The algorithm correctly identifies these cases because the counters for each parity group will not match, returning false.