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

Problem Statement

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.

Intuition

Approach:
Even index alphabets can come only on even, and odd on odd

So we sort the even and odd for both strings

Compare both strings in end

Links

https://leetcode.com/problems/check-if-strings-can-be-made-equal-with-operations-ii/

Video Links

Approach 1:

Sorting

C++

class Solution {
public:
    string find(string &s1){
        string t1_even = "", t1_odd = "";

        for(int i=0; i<s1.size(); i++){
            if(i%2==0)
                t1_even += s1[i];
            else    
                t1_odd += s1[i];
        }

        sort(t1_even.begin(), t1_even.end());
        sort(t1_odd.begin(), t1_odd.end());

        string temp_s1="";
        int i=0,j=0;

        while(i<t1_even.size() or j<t1_odd.size()){
            if(t1_even[i])
                temp_s1 += t1_even[i++];
            if(t1_odd[j])
                temp_s1 += t1_odd[j++];
        }

        return temp_s1;
    }

    bool checkStrings(string s1, string s2) {
        string t1 = find(s1);
        string t2 = find(s2);

        return t1 == t2;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++