2840

2840. Check if Strings Can be Made Equal With Operations II (Medium)

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.

Companies: Citrix

Related Topics:
Hash Table, String, Sorting

Hints:

• Characters in two positions can be swapped if and only if the two positions have the same parity.
• To be able to make the two strings equal, the characters at even and odd positions in the strings should be the same.

Solution 1.

// OJ: https://leetcode.com/problems/check-if-strings-can-be-made-equal-with-operations-ii
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    bool checkStrings(string s, string t) {
        int N = s.size(), cnt[2][26] = {};
        for (int i = 0; i < N; ++i) {
            cnt[i % 2][s[i] - 'a']++;
            cnt[i % 2][t[i] - 'a']--;
        }
        for (int i = 0; i < 26; ++i) {
            if (cnt[0][i] || cnt[1][i]) return false;
        }
        return true;
    }
};