Check if Strings Can be Made Equal With Operations II Solution
Check if Strings Can be Made Equal With Operations II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Check if Strings Can be Made Equal With Operations II is a medium coding problem on strings, hash table and sorting, asked in Google interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Sorting
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given two strings s1 and s2 of the same length n, made of lowercase English letters.
You may apply the following operation to either string, any number of times: choose indices i < j such that j - i is even, and swap the characters at those indices.
Return true if you can make the two strings equal, and false otherwise.
Example 1
Input: s1 = "abcdba", s2 = "cabdab"
Output: true
Explanation: In `s1`, swapping indices 0 and 2 gives `cbadba`, then 2 and 4 gives `cbbdaa`, then 1 and 5 gives `cabdab`.
Example 2
Input: s1 = "abe", s2 = "bea"
Output: false
Explanation: The even positions of `s1` hold `a, e`, but those of `s2` hold `b, a`.
Example 3
Input: s1 = "kata", s2 = "taka"
Output: true
Constraints
n == s1.length == s2.length1 <= n <= 10^5s1 and s2 consist only of lowercase English letters
Hints for Check if Strings Can be Made Equal With Operations II
Hint 1
A swap across an even distance never moves a character between an even index and an odd index.
Hint 2
Within the even indices, any permutation is reachable — adjacent even positions differ by 2, and adjacent swaps generate every permutation. The same holds for the odd indices.
Hint 3
So the strings can be made equal exactly when the letters at even indices match as multisets, and the letters at odd indices match as multisets. Count letters per parity.
How to solve Check if Strings Can be Made Equal With Operations II
Even-distance swaps preserve each character's index parity, and they can rearrange the even-indexed characters (and separately the odd-indexed ones) arbitrarily. So each string is characterised by two multisets — and the strings can meet iff both multisets agree.
Approach
- Keep two arrays of 26 counters,
evenandodd. - For each index
i, add 1 fors1[i]and subtract 1 fors2[i]in the counter array ofi's parity. - Return
trueiff every counter ends at zero.
Why it works
Parity is invariant, so differing multisets on either parity make equality impossible. Conversely, swapping positions i and i + 2 is allowed, and adjacent transpositions of a sequence generate all its permutations, so each parity class of s1 can be sorted into the order s2 needs — only s1 ever has to move.
Complexity
- Time —
O(n) - Space —
O(1) (52 counters)
Pitfalls
- Comparing the whole strings' letter counts ignores parity —
abandbahave equal counts but cannot be made equal. - Sorting each parity class also works but costs
O(n log n).
Reference solution
Python
def checkStrings(s1: str, s2: str) -> bool:
cnt = [[0] * 26 for _ in range(2)]
for i, (a, b) in enumerate(zip(s1, s2)):
cnt[i & 1][ord(a) - 97] += 1
cnt[i & 1][ord(b) - 97] -= 1
return all(v == 0 for row in cnt for v in row)Java
public static boolean checkStrings(String s1, String s2) {
int[] cnt = new int[52];
for (int i = 0; i < s1.length(); i++) {
int base = (i & 1) * 26;
cnt[base + s1.charAt(i) - 'a']++;
cnt[base + s2.charAt(i) - 'a']--;
}
for (int v : cnt) if (v != 0) return false;
return true;
}C++
bool checkStrings(string s1, string s2) {
int cnt[52] = {0};
for (size_t i = 0; i < s1.size(); i++) {
int base = (i & 1) * 26;
cnt[base + s1[i] - 'a']++;
cnt[base + s2[i] - 'a']--;
}
for (int v : cnt) if (v != 0) return false;
return true;
}JavaScript
var checkStrings = function(s1, s2) {
var cnt = new Array(52).fill(0);
for (var i = 0; i < s1.length; i++) {
var base = (i & 1) * 26;
cnt[base + s1.charCodeAt(i) - 97]++;
cnt[base + s2.charCodeAt(i) - 97]--;
}
for (var k = 0; k < 52; k++) if (cnt[k] !== 0) return false;
return true;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets