Check if Strings Can be Made Equal With Operations II - Solution & Explanation
Problem Statement
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:
- Choose any two indices
iandjsuch thati < jand the differencej - iis 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 <= 105s1ands2consist only of lowercase English letters.
Approach Overview
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 1: Approach One: Separate Even and Odd Indexed Characters
This approach involves splitting each string into two separate lists: one containing characters at even indices and the other containing characters at odd indices. This works because you can only swap characters within each group, i.e., even or odd indexed characters.
If the characters present at the even indices of s1 can be rearranged to match the characters at the even indices of s2, and similarly for the characters at the odd indices, then it's possible to make s1 equal to s2.
The C solution manually sorts the characters at even and odd indices separately for both strings s1 and s2 using simple selection sort, and then compares the sorted strings.
Complexity
Time Complexity: O(n^2), Space Complexity: O(1)
Approach 2: Approach Two: Character Frequency Matching for Even and Odd Positions
This approach focuses on character frequencies at even and odd indices. We can make two strings equal by matching the frequency of each character at even indices independently of odd indices because any even index can swap with another even index, and the same goes for odd indices.
Set up two frequency arrays (or hash maps) to count the occurrences of each character at even indices and odd indices in both strings and compare them to check if they are equivalent across both strings.
The C solution uses two frequency arrays to count character occurrences at even and odd indices. It increments the counts for s1 and decrements for s2, and checks whether both frequency lists are zero.
Complexity
Time Complexity: O(n), Space Complexity: O(1)
Approach 3: Counting
We observe the operation in the problem, and find that if the parity of the two indices i and j of the string is the same, then their order can be changed by swapping.
Therefore, we can count the occurrence times of the characters at odd indices and even indices in the two strings. If the counting results of the two strings are the same, then we can make the two strings equal through the operation.
The time complexity is O(n + |\Sigma|), and the space complexity is O(|\Sigma|). Here, n is the length of the string, and \Sigma is the character set.
Similar problems:
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach One: Separate Even and Odd Indexed Characters | Time Complexity: O(n^2), Space Complexity: O(1) |
| Approach Two: Character Frequency Matching for Even and Odd Positions | Time Complexity: O(n), Space Complexity: O(1) |
| Counting | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Check if Strings Can be Made Equal With Operations I and II | 2 Approaches | Leetcode 2839 and 2840 • codestorywithMIK • 9,161 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Check if Strings Can be Made Equal With Operations II easy or hard?
Check if Strings Can be Made Equal With Operations II Python/Java solution
How to solve Check if Strings Can be Made Equal With Operations II in O(n)?
What is the best approach for Check if Strings Can be Made Equal With Operations II?
Is Check if Strings Can be Made Equal With Operations II asked at Google/Amazon/Meta?
What data structure is used in Check if Strings Can be Made Equal With Operations II?
What is the time complexity of Check if Strings Can be Made Equal With Operations II?
Ready to solve this problem?
Practice Check if Strings Can be Made Equal With Operations II with our built-in code editor and test cases.
Practice on FleetCode