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 stringss1 ands2 _equal, and _false otherwise.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3

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

Solution

Method 1 – Parity Group Multiset Comparison

Intuition

Since we can swap any two indices with an even difference, all characters at even indices can be rearranged among themselves, and the same for odd indices. Thus, to make s1 and s2 equal, the multiset of characters at even indices and at odd indices must match between the two strings.

Reasoning

Swapping indices with an even difference allows us to permute the characters at even positions independently from those at odd positions. Therefore, if the sorted characters at even indices in s1 match those in s2, and the same for odd indices, the strings can be made equal.

Approach

  1. Extract the characters at even indices and odd indices from both s1 and s2.
  2. Sort the characters in each group.
  3. Compare the sorted even-indexed characters of s1 and s2, and the sorted odd-indexed characters of s1 and s2.
  4. Return true if both match, otherwise false.

Edge cases:

  • Both strings are already equal.
  • All characters are the same.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    bool canBeEqual(string s1, string s2) {
        vector<char> even1, even2, odd1, odd2;
        for (int i = 0; i < s1.size(); ++i) {
            if (i % 2 == 0) {
                even1.push_back(s1[i]);
                even2.push_back(s2[i]);
            } else {
                odd1.push_back(s1[i]);
                odd2.push_back(s2[i]);
            }
        }
        sort(even1.begin(), even1.end());
        sort(even2.begin(), even2.end());
        sort(odd1.begin(), odd1.end());
        sort(odd2.begin(), odd2.end());
        return even1 == even2 && odd1 == odd2;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func canBeEqual(s1, s2 string) bool {
    even1, even2 := []byte{}, []byte{}
    odd1, odd2 := []byte{}, []byte{}
    for i := range s1 {
        if i%2 == 0 {
            even1 = append(even1, s1[i])
            even2 = append(even2, s2[i])
        } else {
            odd1 = append(odd1, s1[i])
            odd2 = append(odd2, s2[i])
        }
    }
    sort.Slice(even1, func(i, j int) bool { return even1[i] < even1[j] })
    sort.Slice(even2, func(i, j int) bool { return even2[i] < even2[j] })
    sort.Slice(odd1, func(i, j int) bool { return odd1[i] < odd1[j] })
    sort.Slice(odd2, func(i, j int) bool { return odd2[i] < odd2[j] })
    return bytes.Equal(even1, even2) && bytes.Equal(odd1, odd2)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    public boolean canBeEqual(String s1, String s2) {
        char[] even1 = new char[s1.length() / 2 + s1.length() % 2];
        char[] even2 = new char[s2.length() / 2 + s2.length() % 2];
        char[] odd1 = new char[s1.length() / 2];
        char[] odd2 = new char[s2.length() / 2];
        int e = 0, o = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (i % 2 == 0) {
                even1[e] = s1.charAt(i);
                even2[e] = s2.charAt(i);
                e++;
            } else {
                odd1[o] = s1.charAt(i);
                odd2[o] = s2.charAt(i);
                o++;
            }
        }
        Arrays.sort(even1);
        Arrays.sort(even2);
        Arrays.sort(odd1);
        Arrays.sort(odd2);
        return Arrays.equals(even1, even2) && Arrays.equals(odd1, odd2);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun canBeEqual(s1: String, s2: String): Boolean {
        val even1 = mutableListOf<Char>()
        val even2 = mutableListOf<Char>()
        val odd1 = mutableListOf<Char>()
        val odd2 = mutableListOf<Char>()
        for (i in s1.indices) {
            if (i % 2 == 0) {
                even1.add(s1[i])
                even2.add(s2[i])
            } else {
                odd1.add(s1[i])
                odd2.add(s2[i])
            }
        }
        even1.sort(); even2.sort(); odd1.sort(); odd2.sort()
        return even1 == even2 && odd1 == odd2
    }
}
1
2
3
4
5
6
7

class Solution:
    def can_be_equal(self, s1: str, s2: str) -> bool:
        even1 = sorted(s1[::2])
        even2 = sorted(s2[::2])
        odd1 = sorted(s1[1::2])
        odd2 = sorted(s2[1::2])
        return even1 == even2 and odd1 == odd2
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn can_be_equal(s1: String, s2: String) -> bool {
        let even1: Vec<_> = s1.chars().step_by(2).collect();
        let even2: Vec<_> = s2.chars().step_by(2).collect();
        let odd1: Vec<_> = s1.chars().skip(1).step_by(2).collect();
        let odd2: Vec<_> = s2.chars().skip(1).step_by(2).collect();
        let mut even1 = even1; let mut even2 = even2;
        let mut odd1 = odd1; let mut odd2 = odd2;
        even1.sort_unstable(); even2.sort_unstable();
        odd1.sort_unstable(); odd2.sort_unstable();
        even1 == even2 && odd1 == odd2
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), as we sort the even and odd indexed characters of both strings, each of length up to n/2.
  • 🧺 Space complexity: O(n), as we store the even and odd indexed characters for both strings.