# Check if Strings Can be Made Equal With Operations II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/check-if-strings-can-be-made-equal-with-operations-ii)
Canonical: https://scaleengineer.com/dsa/problems/check-if-strings-can-be-made-equal-with-operations-ii
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Hash Table, String
**Companies:** [Citrix](https://scaleengineer.com/companies/citrix)
---
## 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 `i` and `j` such that `i < j` and the difference `j - i` is **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.length`
* `1 <= n <= 105`
* `s1` and `s2` consist only of lowercase English letters.

# Approaches
## Sorting Subsequences
This approach is based on the key insight that the operation allows any permutation of characters at even indices among themselves, and any permutation of characters at odd indices among themselves. Therefore, two strings can be made equal if and only if the multiset of characters at their even indices are identical, and the multiset of characters at their odd indices are also identical. A straightforward way to check if two multisets are identical is to sort them and compare the resulting sequences.
**Time:** O(N log N), where N is the length of the strings. The dominant operation is sorting the subsequences. The length of each subsequence is approximately N/2, so sorting takes O((N/2) log(N/2)), which simplifies to O(N log N). · **Space:** O(N), where N is the length of the strings. We need to store the four subsequences, each of length approximately N/2. This results in a total space complexity proportional to N.
**Pros:** Conceptually simple and easy to understand.; Directly implements the idea of checking multiset equality.
**Cons:** Sub-optimal time complexity due to the sorting step.; Requires extra space proportional to the input string length, which can be significant for large inputs.
### Explanation
The algorithm first separates the characters of each string into two groups: those at even indices and those at odd indices. This is done by iterating through each string and appending characters to the appropriate `StringBuilder`. After separating the characters, we have four subsequences: `s1_even`, `s1_odd`, `s2_even`, and `s2_odd`. To check if the multisets of characters are the same, we convert these subsequences into character arrays and sort them. If the sorted array of even-indexed characters from `s1` is identical to that from `s2`, and the same holds for the odd-indexed characters, it means the strings can be made equal. 

```java
import java.util.Arrays;

class Solution {
    public boolean checkStrings(String s1, String s2) {
        int n = s1.length();
        StringBuilder s1Even = new StringBuilder();
        StringBuilder s1Odd = new StringBuilder();
        StringBuilder s2Even = new StringBuilder();
        StringBuilder s2Odd = new StringBuilder();

        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                s1Even.append(s1.charAt(i));
                s2Even.append(s2.charAt(i));
            } else {
                s1Odd.append(s1.charAt(i));
                s2Odd.append(s2.charAt(i));
            }
        }

        char[] s1EvenChars = s1Even.toString().toCharArray();
        char[] s2EvenChars = s2Even.toString().toCharArray();
        Arrays.sort(s1EvenChars);
        Arrays.sort(s2EvenChars);

        char[] s1OddChars = s1Odd.toString().toCharArray();
        char[] s2OddChars = s2Odd.toString().toCharArray();
        Arrays.sort(s1OddChars);
        Arrays.sort(s2OddChars);

        return Arrays.equals(s1EvenChars, s2EvenChars) && Arrays.equals(s1OddChars, s2OddChars);
    }
}
```
### Algorithm
- Create four `StringBuilder`s: `s1_even`, `s1_odd`, `s2_even`, and `s2_odd`.
- Iterate through the input strings `s1` and `s2` from index `i = 0` to `n-1`.
- If `i` is even, append `s1.charAt(i)` to `s1_even` and `s2.charAt(i)` to `s2_even`.
- If `i` is odd, append `s1.charAt(i)` to `s1_odd` and `s2.charAt(i)` to `s2_odd`.
- Convert the four `StringBuilder`s to character arrays.
- Sort the character arrays corresponding to the even indices (`s1_even`, `s2_even`).
- Sort the character arrays corresponding to the odd indices (`s1_odd`, `s2_odd`).
- Compare the sorted even-indexed arrays and the sorted odd-indexed arrays. If both pairs are equal, return `true`. Otherwise, return `false`.

## Optimized Single-Pass Frequency Counting
This approach improves upon the sorting method by using frequency counting, which is more efficient for checking multiset equality when the alphabet size is small and fixed. Instead of sorting, we count the occurrences of each character for the even and odd indexed subsequences. By using a clever trick of incrementing counts for `s1` and decrementing for `s2` in a single pass, we can determine if the character distributions match with optimal time and space complexity.
**Time:** O(N), where N is the length of the strings. We perform a single pass through the strings of length N, and then two constant-time loops of size 26. The overall complexity is dominated by the first loop. · **Space:** O(1). We use two arrays of a fixed size (26) to store the character counts. The space required does not depend on the input string length N, making it constant.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1).; Efficient in practice due to a single pass and array-based operations.
**Cons:** Slightly less direct than the sorting approach, as it relies on the frequency counting trick.
### Explanation
The core idea remains that the multiset of characters at even indices must match, and the same for odd indices. We use two arrays of size 26, one for even-indexed characters and one for odd-indexed, to track the balance of characters between `s1` and `s2`. We iterate through both strings simultaneously. For each character in `s1`, we increment its count in the corresponding array (even/odd), and for each character in `s2`, we decrement its count. If, at the end, both strings have the same character distribution for even and odd positions, all counts in our frequency arrays will cancel out and become zero. A final check of the arrays confirms this. If any count is non-zero, the strings cannot be made equal.

```java
class Solution {
    public boolean checkStrings(String s1, String s2) {
        int n = s1.length();
        int[] evenCounts = new int[26];
        int[] oddCounts = new int[26];

        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                evenCounts[s1.charAt(i) - 'a']++;
                evenCounts[s2.charAt(i) - 'a']--;
            } else {
                oddCounts[s1.charAt(i) - 'a']++;
                oddCounts[s2.charAt(i) - 'a']--;
            }
        }

        for (int i = 0; i < 26; i++) {
            if (evenCounts[i] != 0 || oddCounts[i] != 0) {
                return false;
            }
        }

        return true;
    }
}
```
### Algorithm
- Create two integer arrays, `evenCounts` and `oddCounts`, each of size 26, to store frequency differences. Initialize them to all zeros.
- Iterate through the strings from `i = 0` to `n-1` in a single loop.
- If index `i` is even, increment the count for `s1.charAt(i)` in `evenCounts` and decrement the count for `s2.charAt(i)` in the same array.
- If index `i` is odd, perform the same increment/decrement operations on the `oddCounts` array.
- After the loop, iterate through both `evenCounts` and `oddCounts` arrays. If any element is not zero, it means the character frequencies do not match, so return `false`.
- If both arrays contain only zeros, return `true`.

# Solutions
### Java

```java
class Solution {
public
  boolean checkStrings(String s1, String s2) {
    int[][] cnt = new int[2][26];
    for (int i = 0; i < s1.length(); ++i) {
      ++cnt[i & 1][s1.charAt(i) - 'a'];
      --cnt[i & 1][s2.charAt(i) - 'a'];
    }
    for (int i = 0; i < 26; ++i) {
      if (cnt[0][i] != 0 || cnt[1][i] != 0) {
        return false;
      }
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool checkStrings(string s1, string s2) {
    vector<vector<int>> cnt(2, vector<int>(26, 0));
    for (int i = 0; i < s1.size(); ++i) {
      ++cnt[i & 1][s1[i] - 'a'];
      --cnt[i & 1][s2[i] - 'a'];
    }
    for (int i = 0; i < 26; ++i) {
      if (cnt[0][i] || cnt[1][i]) {
        return false;
      }
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def checkStrings(self, s1: str, s2: str) -> bool: return sorted(
        s1[:: 2]) == sorted(s2[:: 2]) and sorted(s1[1:: 2]) == sorted(s2[1:: 2])

```