Check if Strings Can be Made Equal With Operations II
Problem
You are given two strings s1 and s2 of equal length n, made of lowercase letters. On either string you may, any number of times, swap two characters at indices i < j whenever j − i is even. Return true if s1 can be made equal to s2, else false.
Since j − i being even means i and j share the same parity, characters can move freely within the even positions and freely within the odd positions, but never cross between the two. So the strings can be matched iff their even-position letters form the same multiset and their odd-position letters form the same multiset.
s1 = "abcdba", s2 = "cabdab"truedef checkStrings(s1, s2):
# Same-parity swaps let us freely permute even-index chars
# and (separately) odd-index chars. So s1 and s2 match iff
# their even buckets and odd buckets are equal as multisets.
even1, odd1 = [0] * 26, [0] * 26
even2, odd2 = [0] * 26, [0] * 26
for i in range(len(s1)):
if i % 2 == 0:
even1[ord(s1[i]) - 97] += 1
even2[ord(s2[i]) - 97] += 1
else:
odd1[ord(s1[i]) - 97] += 1
odd2[ord(s2[i]) - 97] += 1
return even1 == even2 and odd1 == odd2function checkStrings(s1, s2) {
// Same-parity swaps let us freely permute even-index chars
// and (separately) odd-index chars, so compare the two buckets.
const even1 = new Array(26).fill(0), odd1 = new Array(26).fill(0);
const even2 = new Array(26).fill(0), odd2 = new Array(26).fill(0);
for (let i = 0; i < s1.length; i++) {
const a = s1.charCodeAt(i) - 97, b = s2.charCodeAt(i) - 97;
if (i % 2 === 0) { even1[a]++; even2[b]++; }
else { odd1[a]++; odd2[b]++; }
}
const same = (p, q) => p.every((v, k) => v === q[k]);
return same(even1, even2) && same(odd1, odd2);
}boolean checkStrings(String s1, String s2) {
// Same-parity swaps freely permute even-index chars and
// (separately) odd-index chars; compare the two buckets.
int[] even1 = new int[26], odd1 = new int[26];
int[] even2 = new int[26], odd2 = new int[26];
for (int i = 0; i < s1.length(); i++) {
int a = s1.charAt(i) - 'a', b = s2.charAt(i) - 'a';
if (i % 2 == 0) { even1[a]++; even2[b]++; }
else { odd1[a]++; odd2[b]++; }
}
return Arrays.equals(even1, even2) && Arrays.equals(odd1, odd2);
}bool checkStrings(string s1, string s2) {
// Same-parity swaps freely permute even-index chars and
// (separately) odd-index chars; compare the two buckets.
int even1[26] = {}, odd1[26] = {};
int even2[26] = {}, odd2[26] = {};
for (int i = 0; i < (int)s1.size(); i++) {
int a = s1[i] - 'a', b = s2[i] - 'a';
if (i % 2 == 0) { even1[a]++; even2[b]++; }
else { odd1[a]++; odd2[b]++; }
}
return equal(even1, even1 + 26, even2)
&& equal(odd1, odd1 + 26, odd2);
}Explanation
The whole problem hinges on what a swap can reach. We may swap indices i and j only when j − i is even, which is exactly when i and j have the same parity (both even or both odd).
Because we can perform such swaps any number of times, every even index can reach every other even index, and every odd index can reach every other odd index. So the characters sitting on even positions can be reordered into any arrangement we like, and likewise for the odd positions — but a character can never hop from an even slot to an odd slot.
That splits each string into two independent buckets: the even-index characters and the odd-index characters. Two strings can be made equal exactly when the even bucket of s1 is a permutation of the even bucket of s2, and the odd bucket of s1 is a permutation of the odd bucket of s2.
To test “is a permutation of”, we just compare letter multisets. We keep four count arrays of length 26 — even/odd for each string — sweep through the indices once, and increment the right bucket based on the index parity. At the end the answer is true iff even1 == even2 and odd1 == odd2.
Example: s1 = "abcdba", s2 = "cabdab". Even positions (0, 2, 4) give a c b for both → {a, b, c}. Odd positions (1, 3, 5) give b d a for both → {a, b, d}. Both buckets match, so the answer is true. Contrast s1 = "abe", s2 = "bea": the even bucket of s1 is {a, e} but of s2 is {b, a}, which differ, so the answer is false.