Check if Strings Can be Made Equal With Operations II solution and explanation
Google
9 more videos on this problem
Check if Strings Can be Made Equal With Operations I and II | 2 Approaches | Leetcode 2839 and 2840codestorywithMIK · 30:44 · 9K views
Leetcode BiWeekly contest 112 - Medium - Check if Strings Can be Made Equal With Operations IIPrakhar Agrawal · 7:54 · 1K views
2840. Check if Strings Can be Made Equal With Operations II | Leetcode Daily - PythonLeetcode Daily · 4:54 · 547 views
2840. Check if Strings Can be Made Equal With Operations II (Leetcode Medium)Programming Live with Larry · 5:53 · 436 views
Daily Leetcode #2190: Mar 30, 2026 - 2840. Check if Strings Can be Made Equal With Operations IIProgramming Live with Larry · 5:19 · 326 views
Check if Strings Can be Made Equal With Operations II | LeetCode 2840 | Java Code | Developer CoderDeveloper Coder · 14:42 · 233 views
Check if Strings Can be Made Equal With Operations II | LeetCode 2840 - Pythonimpoldev · 10:09 · 217 views
Check if Strings Can be Made Equal With Operations II - Leetcode 2840 | Java - Hindi | Daily LCKernel Queen 👑 · 6:05 · 214 views
Check if strings can be made equal with Operations 2 | Leetcode 2840 |C++| Leetcode Daily ChallengePushkar Sehrawat · 13:47 · 172 views
Leetcode | 2840 Check if Strings Can be MAde Equal With Operations II |Java | Simple Trick| HashingCakot Coding · 7:28 · 113 views
The problem
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.
def can_be_equal(s1, s2):
s1_even = sorted(s1[i] for i in range(len(s1)) if i % 2 == 0)
s1_odd = sorted(s1[i] for i in range(len(s1)) if i % 2 != 0)
s2_even = sorted(s2[i] for i in range(len(s2)) if i % 2 == 0)
s2_odd = sorted(s2[i] for i in range(len(s2)) if i % 2 != 0)
return s1_even == s2_even and s1_odd == s2_oddimport java.util.Arrays;
public class Solution {
public boolean canBeEqual(String s1, String s2) {
char[] s1_even = new char[(s1.length() + 1) / 2];
char[] s1_odd = new char[s1.length() / 2];
char[] s2_even = new char[(s2.length() + 1) / 2];
char[] s2_odd = new char[s2.length() / 2];
for (int i = 0, e = 0, o = 0; i < s1.length(); i++) {
if (i % 2 == 0) {
s1_even[e] = s1.charAt(i);
s2_even[e++] = s2.charAt(i);
} else {
s1_odd[o] = s1.charAt(i);
s2_odd[o++] = s2.charAt(i);
}
}
Arrays.sort(s1_even);
Arrays.sort(s1_odd);
Arrays.sort(s2_even);
Arrays.sort(s2_odd);
return Arrays.equals(s1_even, s2_even) && Arrays.equals(s1_odd, s2_odd);
}
}#include <algorithm>
#include <string>
#include <iostream>
bool canBeEqual(std::string s1, std::string s2) {
std::string s1_even, s1_odd, s2_even, s2_odd;
for (size_t i = 0; i < s1.size(); ++i) {
if (i % 2 == 0) {
s1_even += s1[i];
s2_even += s2[i];
} else {
s1_odd += s1[i];
s2_odd += s2[i];
}
}
std::sort(s1_even.begin(), s1_even.end());
std::sort(s1_odd.begin(), s1_odd.end());
std::sort(s2_even.begin(), s2_even.end());
std::sort(s2_odd.begin(), s2_odd.end());
return s1_even == s2_even && s1_odd == s2_odd;
}function canBeEqual(s1, s2) {
const s1_even = s1.split('').filter((_, i) => i % 2 === 0).sort().join('');
const s1_odd = s1.split('').filter((_, i) => i % 2 !== 0).sort().join('');
const s2_even = s2.split('').filter((_, i) => i % 2 === 0).sort().join('');
const s2_odd = s2.split('').filter((_, i) => i % 2 !== 0).sort().join('');
return s1_even === s2_even && s1_odd === s2_odd;
}#include <stdbool.h>
#include <string.h>
bool canBeEqual(char *s1, char *s2) {
int n = strlen(s1);
for (int i = 0; i < n; i++) {
for (int j = i + 2; j < n; j += 2) {
if (s1[i] > s1[j]) {
char temp = s1[i];
s1[i] = s1[j];
s1[j] = temp;
}
if (s2[i] > s2[j]) {
char temp = s2[i];
s2[i] = s2[j];
s2[j] = temp;
}
}
}
return strcmp(s1, s2) == 0;
}using System;
using System.Linq;
public class Solution {
public bool CanBeEqual(string s1, string s2) {
var s1_even = s1.Where((_, i) => i % 2 == 0).OrderBy(c => c).ToArray();
var s1_odd = s1.Where((_, i) => i % 2 != 0).OrderBy(c => c).ToArray();
var s2_even = s2.Where((_, i) => i % 2 == 0).OrderBy(c => c).ToArray();
var s2_odd = s2.Where((_, i) => i % 2 != 0).OrderBy(c => c).ToArray();
return s1_even.SequenceEqual(s2_even) && s1_odd.SequenceEqual(s2_odd);
}
}The Python solution creates two sorted lists for even and odd indexed characters of both s1 and s2. The function checks if these sorted lists are equal, which determines if the strings can be made equal.
Time Complexity: O(n log n), Space Complexity: O(n)
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.
def can_be_equal(s1, s2):
freq = [[0] * 26, [0] * 26]
for i in range(len(s1)):
freq[i % 2][ord(s1[i]) - ord('a')] += 1
freq[i % 2][ord(s2[i]) - ord('a')] -= 1
return all(f == 0 for row in freq for f in row)public class Solution {
public boolean canBeEqual(String s1, String s2) {
int[][] freq = new int[2][26];
for (int i = 0; i < s1.length(); i++) {
freq[i % 2][s1.charAt(i) - 'a']++;
freq[i % 2][s2.charAt(i) - 'a']--;
}
for (int i = 0; i < 26; i++) {
if (freq[0][i] != 0 || freq[1][i] != 0) return false;
}
return true;
}
}#include <vector>
#include <string>
using namespace std;
bool canBeEqual(string s1, string s2) {
vector<vector<int>> freq(2, vector<int>(26, 0));
for (size_t i = 0; i < s1.length(); ++i) {
freq[i % 2][s1[i] - 'a']++;
freq[i % 2][s2[i] - 'a']--;
}
for (int i = 0; i < 26; ++i) {
if (freq[0][i] != 0 || freq[1][i] != 0) return false;
}
return true;
}function canBeEqual(s1, s2) {
let freq = [Array(26).fill(0), Array(26).fill(0)];
for (let i = 0; i < s1.length; i++) {
freq[i % 2][s1.charCodeAt(i) - 'a'.charCodeAt(0)]++;
freq[i % 2][s2.charCodeAt(i) - 'a'.charCodeAt(0)]--;
}
for (let i = 0; i < 26; i++) {
if (freq[0][i] !== 0 || freq[1][i] !== 0) return false;
}
return true;
}#include <stdbool.h>
#include <string.h>
bool canBeEqual(char *s1, char *s2) {
int count1[2][26] = {0};
int n = strlen(s1);
for (int i = 0; i < n; i++) {
count1[i % 2][s1[i] - 'a']++;
count1[i % 2][s2[i] - 'a']--;
}
for (int i = 0; i < 26; i++) {
if (count1[0][i] != 0 || count1[1][i] != 0) {
return false;
}
}
return true;
}public class Solution {
public bool CanBeEqual(string s1, string s2) {
int[,] freq = new int[2, 26];
for (int i = 0; i < s1.Length; i++) {
freq[i % 2, s1[i] - 'a']++;
freq[i % 2, s2[i] - 'a']--;
}
for (int i = 0; i < 26; i++) {
if (freq[0, i] != 0 || freq[1, i] != 0) return false;
}
return true;
}
}In Python, the solution calculates character frequencies at even and odd indices using lists of size 26 (for each alphabet letter) and checks if differences are nullified across both strings.
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:
function checkStrings(s1: string, s2: string): boolean {
const cnt: number[][] = Array.from({ length: 2 }, () => Array.from({ length: 26 }, () => 0));
for (let i = 0; i < s1.length; ++i) {
++cnt[i & 1][s1.charCodeAt(i) - 97];
--cnt[i & 1][s2.charCodeAt(i) - 97];
}
return cnt.every(arr => arr.every(x => x === 0));
}func checkStrings(s1 string, s2 string) bool {
cnt := [2][26]int{}
for i := 0; i < len(s1); i++ {
cnt[i&1][s1[i]-'a']++
cnt[i&1][s2[i]-'a']--
}
for i := 0; i < 26; i++ {
if cnt[0][i] != 0 || cnt[1][i] != 0 {
return false
}
}
return true
}impl Solution {
pub fn check_strings(s1: String, s2: String) -> bool {
let mut cnt: [[i32; 26]; 2] = [[0; 26]; 2];
let n = s1.len();
let s1 = s1.as_bytes();
let s2 = s2.as_bytes();
for i in 0..n {
let idx = (i & 1) as usize;
cnt[idx][(s1[i] - b'a') as usize] += 1;
cnt[idx][(s2[i] - b'a') as usize] -= 1;
}
cnt.iter().all(|row| row.iter().all(|&x| x == 0))
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach One: Separate Even and Odd Indexed Characters | Time Complexity: O(n log n), Space Complexity: O(n) |
| Approach Two: Character Frequency Matching for Even and Odd Positions | Time Complexity: O(n), Space Complexity: O(1) |
| Counting | – |
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 |
Frequently asked questions
Is Check if Strings Can be Made Equal With Operations II easy or hard?
The problem is classified as Medium difficulty. The main challenge is recognizing that allowed swaps preserve index parity, which splits the string into two independent groups that can be rearranged internally.
Check if Strings Can be Made Equal With Operations II Python/Java solution
A typical Python or Java implementation iterates through both strings and updates two frequency arrays based on index parity. Characters from even positions are counted separately from odd positions. After processing the strings, matching frequencies confirm that the transformation is possible.
How to solve Check if Strings Can be Made Equal With Operations II in O(n)?
Iterate through both strings once and maintain frequency arrays for even and odd positions. Increment counts for characters in s1 and decrement for characters in s2 within the same parity bucket. If all frequency values end at zero, both parity groups contain identical characters and the strings can be made equal.
What is the best approach for Check if Strings Can be Made Equal With Operations II?
The best approach is character frequency matching for even and odd positions. Since swaps are allowed only between indices of the same parity, characters at even indices and odd indices form independent groups. Counting frequencies for both groups and verifying they match across the two strings solves the problem in O(n) time and O(1) space.
Is Check if Strings Can be Made Equal With Operations II asked at Google/Amazon/Meta?
Parity-based string manipulation and frequency comparison problems commonly appear in interviews at companies like Amazon, Google, and Meta. Variants of this problem test understanding of invariants, string hashing, and character frequency techniques.
What data structure is used in Check if Strings Can be Made Equal With Operations II?
The optimal solution uses a hash table or fixed-size frequency array to track character counts for even and odd indices. Because the alphabet size is small (typically lowercase English letters), an integer array of size 26 is usually sufficient.
What is the time complexity of Check if Strings Can be Made Equal With Operations II?
The optimal solution runs in O(n) time where n is the length of the string. A single pass counts characters at even and odd indices separately for both strings. The alternative sorting-based approach requires O(n log n) time due to sorting the parity groups.