LeetCode 2839 - Check if Strings Can be Made Equal With Operations I

The problem gives us two strings, s1 and s2, each containing exactly four lowercase English letters. We are allowed to repeatedly perform a very specific swap operation on either string.

leetcodeeasystring

LeetCode Problem 2839

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

The problem gives us two strings, s1 and s2, each containing exactly four lowercase English letters. We are allowed to repeatedly perform a very specific swap operation on either string. In one operation, we may choose two indices i and j such that j - i = 2, then swap the characters at those positions.

Because the strings are length 4, the only valid swaps are:

  • Swap indices 0 and 2
  • Swap indices 1 and 3

The goal is to determine whether it is possible to transform one string into the other using these operations any number of times.

The key observation is that the operation never allows characters to move between even and odd indices. Characters at indices 0 and 2 can only swap with each other, and characters at indices 1 and 3 can only swap with each other.

This means:

  • The characters originally located at even positions must match between the two strings, ignoring order.
  • The characters originally located at odd positions must also match between the two strings, ignoring order.

The constraints are extremely small since both strings always have length 4. This means even brute-force solutions are feasible, but the problem is really testing whether we can identify the structural property created by the allowed swap operation.

An important detail is that repeated swaps are allowed. Since swapping the same pair multiple times can rearrange the two positions freely, the order inside each parity group does not matter. However, characters can never cross between parity groups.

Some edge cases that could trip up a naive implementation include repeated characters, strings that are already equal, and cases where the same characters exist overall but are distributed differently across even and odd positions.

Approaches

Brute Force Approach

A brute-force solution would try every reachable configuration of the string by repeatedly applying the allowed swaps. Since there are only two possible swaps, we can generate all reachable states using breadth-first search or depth-first search.

Starting from s1, we repeatedly:

  1. Swap indices (0, 2)
  2. Swap indices (1, 3)

We store all visited strings to avoid infinite loops. If we ever reach s2, we return true.

This approach is correct because it explicitly explores every possible string reachable through the allowed operations.

Although the constraints are tiny and this works fine here, it is unnecessarily complicated for such a structured problem. The main weakness is that it treats the problem as a generic graph search instead of exploiting the mathematical property of the swaps.

Optimal Approach

The better solution comes from observing how the swaps behave.

The allowed operations only swap characters within the same parity:

  • Even indices: 0 and 2
  • Odd indices: 1 and 3

Therefore:

  • Characters at even positions can be rearranged freely among even positions.
  • Characters at odd positions can be rearranged freely among odd positions.
  • Even-position characters can never move to odd positions, and vice versa.

So the problem reduces to checking whether:

  • The multiset of even-index characters in s1 matches the multiset of even-index characters in s2
  • The multiset of odd-index characters in s1 matches the multiset of odd-index characters in s2

We can simply sort the two even-character pairs and the two odd-character pairs, then compare them.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(1) O(1) Explores all reachable states using BFS or DFS
Optimal O(1) O(1) Compares even and odd index character groups

Algorithm Walkthrough

  1. Extract the characters at even indices from s1.

These are the characters at indices 0 and 2. Since only even positions can swap with each other, these characters form one independent group. 2. Extract the characters at odd indices from s1.

These are the characters at indices 1 and 3. They form the second independent group. 3. Repeat the same extraction for s2.

We now have four groups:

  • Even characters from s1
  • Odd characters from s1
  • Even characters from s2
  • Odd characters from s2
  1. Sort each group.

Sorting removes the effect of ordering. Since swaps allow arbitrary rearrangement inside each parity group, only the character counts matter. 5. Compare the sorted even groups and sorted odd groups.

If both pairs match, then the transformation is possible. Otherwise, it is impossible. 6. Return the result of the comparison.

Why it works

The operation preserves index parity. A character starting at an even index can only ever appear at an even index, and similarly for odd indices. Therefore, the even-index character multiset and odd-index character multiset are invariants of the process.

If these invariants match between the two strings, we can rearrange characters within each parity group to obtain the target string. If they do not match, no sequence of allowed swaps can ever produce the target.

Python Solution

class Solution:
    def canBeEqual(self, s1: str, s2: str) -> bool:
        even_s1 = sorted([s1[0], s1[2]])
        odd_s1 = sorted([s1[1], s1[3]])

        even_s2 = sorted([s2[0], s2[2]])
        odd_s2 = sorted([s2[1], s2[3]])

        return even_s1 == even_s2 and odd_s1 == odd_s2

The implementation directly follows the parity-group observation.

First, we collect the even-index characters from both strings. These are the only characters that can swap with each other. Then we do the same for the odd-index characters.

We sort each pair so that order no longer matters. For example, ['a', 'c'] and ['c', 'a'] become identical after sorting.

Finally, we compare the even groups and odd groups separately. Both must match for the transformation to be possible.

Because the string length is fixed at four, this implementation runs in constant time and uses constant extra space.

Go Solution

import "sort"

func canBeEqual(s1 string, s2 string) bool {
    evenS1 := []byte{s1[0], s1[2]}
    oddS1 := []byte{s1[1], s1[3]}

    evenS2 := []byte{s2[0], s2[2]}
    oddS2 := []byte{s2[1], s2[3]}

    sort.Slice(evenS1, func(i, j int) bool {
        return evenS1[i] < evenS1[j]
    })

    sort.Slice(oddS1, func(i, j int) bool {
        return oddS1[i] < oddS1[j]
    })

    sort.Slice(evenS2, func(i, j int) bool {
        return evenS2[i] < evenS2[j]
    })

    sort.Slice(oddS2, func(i, j int) bool {
        return oddS2[i] < oddS2[j]
    })

    return string(evenS1) == string(evenS2) &&
        string(oddS1) == string(oddS2)
}

The Go implementation follows the same logic as the Python version.

Since Go strings are immutable, we extract the relevant characters into byte slices before sorting them. We use sort.Slice to sort each two-character slice independently.

There are no concerns about integer overflow or large memory usage because the input size is fixed and extremely small.

Worked Examples

Example 1

Input:

s1 = "abcd"
s2 = "cdab"

Step 1: Extract parity groups

String Even Indices (0,2) Odd Indices (1,3)
s1 ['a', 'c'] ['b', 'd']
s2 ['c', 'a'] ['d', 'b']

Step 2: Sort groups

String Sorted Even Sorted Odd
s1 ['a', 'c'] ['b', 'd']
s2 ['a', 'c'] ['b', 'd']

Step 3: Compare

Both even groups match and both odd groups match.

Result:

true

Example 2

Input:

s1 = "abcd"
s2 = "dacb"

Step 1: Extract parity groups

String Even Indices (0,2) Odd Indices (1,3)
s1 ['a', 'c'] ['b', 'd']
s2 ['d', 'c'] ['a', 'b']

Step 2: Sort groups

String Sorted Even Sorted Odd
s1 ['a', 'c'] ['b', 'd']
s2 ['c', 'd'] ['a', 'b']

Step 3: Compare

The even groups do not match.

Result:

false

Complexity Analysis

Measure Complexity Explanation
Time O(1) Only a fixed number of characters are processed
Space O(1) Uses a constant amount of extra storage

The algorithm operates on strings of length exactly four, so the amount of work never grows with input size. Even though sorting is used, the sorted arrays always contain only two elements, making the runtime effectively constant.

Test Cases

solution = Solution()

assert solution.canBeEqual("abcd", "cdab") is True  # provided example, valid swaps
assert solution.canBeEqual("abcd", "dacb") is False  # provided example, parity mismatch

assert solution.canBeEqual("abcd", "abcd") is True  # already equal
assert solution.canBeEqual("abdc", "acbd") is False  # impossible parity movement
assert solution.canBeEqual("zzzz", "zzzz") is True  # all characters identical

assert solution.canBeEqual("abab", "bbaa") is False  # same total chars, wrong parity groups
assert solution.canBeEqual("aabb", "bbaa") is True  # parity groups match after swaps

assert solution.canBeEqual("xyzw", "xwzy") is True  # odd positions swapped
assert solution.canBeEqual("xyzw", "zyxw") is True  # even positions swapped
assert solution.canBeEqual("xyzw", "wxyz") is False  # parity groups incompatible

Test Summary

Test Why
"abcd", "cdab" Valid transformation using both swaps
"abcd", "dacb" Impossible due to parity mismatch
"abcd", "abcd" Already equal strings
"abdc", "acbd" Characters cannot cross parity groups
"zzzz", "zzzz" Repeated identical characters
"abab", "bbaa" Same letters overall, invalid parity distribution
"aabb", "bbaa" Duplicate letters with valid parity grouping
"xyzw", "xwzy" Odd-index swap only
"xyzw", "zyxw" Even-index swap only
"xyzw", "wxyz" Both parity groups invalid

Edge Cases

One important edge case is when the strings are already equal. A careless implementation might attempt unnecessary transformations or incorrectly assume at least one swap is required. Our solution handles this naturally because both parity groups already match.

Another important case involves repeated characters. For example, "aabb" and "bbaa" can still be transformed into each other because the even-index groups and odd-index groups contain the same characters after sorting. The algorithm correctly treats parity groups as multisets rather than ordered sequences.

A third edge case occurs when the strings contain the same overall characters but distributed across different parity positions. For example, "abab" and "bbaa" contain identical character counts globally, but characters would need to move between even and odd indices to complete the transformation. Since the allowed operations never permit parity changes, the algorithm correctly returns false.

A subtle case is when only one parity group matches. For example, the even-index characters may align perfectly while the odd-index characters differ. The implementation independently checks both groups, ensuring partial matches do not incorrectly produce a positive result.