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
andj
such thatj - 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
|
|
Example 2
|
|
Constraints
s1.length == s2.length == 4
s1
ands2
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
- Extract the characters at even indices and odd indices from both
s1
ands2
. - Sort the characters in each group.
- Compare the sorted even-indexed characters of
s1
ands2
, and the sorted odd-indexed characters ofs1
ands2
. - Return true if both match, otherwise false.
Edge cases:
- Both strings are already equal.
- All characters are the same.
Code
|
|
|
|
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.