Problem

You are given two strings s1 and s2, both of length 4, 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 j - i = 2, then swap the two characters at those indices in the string.

Return true if you can make the stringss1 ands2 equal, andfalse otherwise.

Examples

Example 1

1
2
3
4
5
Input: s1 = "abcd", s2 = "cdab"
Output: true
Explanation: We can do the following operations on s1:
- Choose the indices i = 0, j = 2. The resulting string is s1 = "cbad".
- Choose the indices i = 1, j = 3. The resulting string is s1 = "cdab" = s2.

Example 2

1
2
3
Input: s1 = "abcd", s2 = "dacb"
Output: false
Explanation: It is not possible to make the two strings equal.

Constraints

  • s1.length == s2.length == 4
  • s1 and s2 consist only of lowercase English letters.

Solution

Method 1 – Parity Group Comparison

Intuition

Since we can swap characters at indices with a difference of 2 any number of times, the 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 a difference of 2 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
class Solution {
    public boolean canBeEqual(String s1, String s2) {
        char[] even1 = {s1.charAt(0), s1.charAt(2)};
        char[] even2 = {s2.charAt(0), s2.charAt(2)};
        char[] odd1 = {s1.charAt(1), s1.charAt(3)};
        char[] odd2 = {s2.charAt(1), s2.charAt(3)};
        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
class Solution:
    def can_be_equal(self, s1: str, s2: str) -> bool:
        even1 = sorted([s1[0], s1[2]])
        even2 = sorted([s2[0], s2[2]])
        odd1 = sorted([s1[1], s1[3]])
        odd2 = sorted([s2[1], s2[3]])
        return even1 == even2 and odd1 == odd2

Complexity

  • ⏰ Time complexity: O(1), as the strings are of fixed length 4 and all operations are constant time.
  • 🧺 Space complexity: O(1), as only a constant number of variables are used.