Check if Strings Can be Made Equal With Operations II

Medium
1806.

Check if Strings Can be Made Equal With Operations II

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.

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.length
  • 1 <= n <= 10^5
  • s1 and s2 consist only of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkStrings = function(s1, s2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.length
  • 1 <= n <= 10^5
  • s1 and s2 consist only of lowercase English letters

Hints for Check if Strings Can be Made Equal With Operations II

  1. Hint 1

    A swap across an even distance never moves a character between an even index and an odd index.

  2. 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.

  3. 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

  1. Keep two arrays of 26 counters, even and odd.
  2. For each index i, add 1 for s1[i] and subtract 1 for s2[i] in the counter array of i's parity.
  3. Return true iff 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 — ab and ba have 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