Watch 10 video solutions for Check if Strings Can be Made Equal With Operations II, a medium level problem involving Hash Table, String, Sorting. This walkthrough by codestorywithMIK has 8,435 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two strings s1 and s2, both of length n, consisting of lowercase English letters.
You can apply the following operation on any of the two strings any number of times:
i and j such that i < j and the difference j - i is even, then swap the two characters at those indices in the string.Return true if you can make the strings s1 and s2 equal, and false otherwise.
Example 1:
Input: s1 = "abcdba", s2 = "cabdab" Output: true Explanation: We can apply the following operations on s1: - Choose the indices i = 0, j = 2. The resulting string is s1 = "cbadba". - Choose the indices i = 2, j = 4. The resulting string is s1 = "cbbdaa". - Choose the indices i = 1, j = 5. The resulting string is s1 = "cabdab" = s2.
Example 2:
Input: s1 = "abe", s2 = "bea" Output: false Explanation: It is not possible to make the two strings equal.
Constraints:
n == s1.length == s2.length1 <= n <= 105s1 and s2 consist only of lowercase English letters.Problem Overview: You are given two strings s1 and s2 of equal length. An operation allows swapping characters whose indices differ by an even number, which effectively means you can freely swap characters among even indices and among odd indices. The task is to check whether these operations can transform s1 into s2.
Approach 1: Separate Even and Odd Indexed Characters (O(n log n) time, O(n) space)
The key observation: swaps only occur between indices with the same parity. That means all characters at even indices can be rearranged among themselves, and the same applies to odd indices. Extract characters from even positions of both strings into two lists, and do the same for odd positions. Sort each list and compare corresponding groups. If the sorted even groups match and the sorted odd groups match, the strings can be made equal. This approach uses sorting to normalize the order of characters inside each parity group.
Approach 2: Character Frequency Matching for Even and Odd Positions (O(n) time, O(1) space)
Sorting is unnecessary if you only care about character counts. Instead, maintain two frequency counters: one for even indices and one for odd indices. Traverse both strings simultaneously and update counts for each parity position. For example, increment the count for s1[i] and decrement the count for s2[i] within the corresponding parity bucket. If all counts return to zero after the pass, both strings contain identical characters in even positions and identical characters in odd positions. This uses a classic hash table or fixed-size frequency array technique commonly applied in string comparison problems.
Recommended for interviews: The frequency-counting approach is the expected optimal solution. It runs in linear time and constant extra space, which signals strong understanding of constraints and parity-based invariants. The sorting approach is still valid and easier to reason about initially, so many candidates mention it first before optimizing to the frequency method.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Separate Even and Odd Indexed Characters (Sorting) | O(n log n) | O(n) | Good first approach when reasoning about allowed swaps and grouping characters by parity |
| Character Frequency Matching for Even and Odd Positions | O(n) | O(1) | Optimal approach when strings contain limited character set and only frequency comparison is needed |