Check if Strings Can be Made Equal With Operations I Solution
Check if Strings Can be Made Equal With Operations I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Check if Strings Can be Made Equal With Operations I is an easy coding problem on strings, asked in Google interviews.
- Difficulty: Easy
- Topics: Strings
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given two strings s1 and s2, each of length exactly 4 and made of lowercase letters.
You may apply the following operation to either string as many times as you like: pick two indices i and j with j - i = 2 and swap the characters at those indices.
Return true if you can make s1 and s2 equal, and false otherwise.
Example 1
Input: s1 = "abcd", s2 = "cdab"
Output: true
Explanation: Swap indices 0 and 2 of s1 to get "cbad", then indices 1 and 3 to get "cdab".
Example 2
Input: s1 = "abcd", s2 = "dacb"
Output: false
Explanation: Index 0 of s2 holds 'd', but only 'a' or 'c' can ever reach index 0 of s1.
Example 3
Input: s1 = "kair", s2 = "kair"
Output: true
Explanation: The strings are already equal; no operation is needed.
Constraints
s1.length == s2.length == 4s1 and s2 consist only of lowercase English letters
Hints for Check if Strings Can be Made Equal With Operations I
Hint 1
A swap with
j - i = 2only ever moves characters between index 0 and index 2, or between index 1 and index 3.Hint 2
So each string splits into two independent pairs: positions
{0, 2}and positions{1, 3}. Within a pair the two characters can be in either order.Hint 3
The strings can be made equal exactly when the pair at
{0, 2}holds the same two characters in both strings, and likewise for{1, 3}.
How to solve Check if Strings Can be Made Equal With Operations I
The allowed swaps never mix the even positions with the odd positions; within each group of two the characters can be ordered freely. So all that matters is the unordered pair at {0, 2} and the unordered pair at {1, 3}.
Approach
- Check that
{s1[0], s1[2]}equals{s2[0], s2[2]}as an unordered pair — eithers1[0] == s2[0] && s1[2] == s2[2]or the crossed version. - Check the same for indices 1 and 3.
- Return
trueonly if both checks pass.
Why it works
Each operation permutes the characters inside one of the two groups, so the multiset of each group is invariant — the condition is necessary. It is also sufficient: if a group's characters are the same two but in the other order, one swap on s1 fixes it.
Complexity
- Time —
O(1) - Space —
O(1)
Pitfalls
- Comparing the sorted whole strings is wrong — a character cannot move from an even to an odd index ("abcd" vs "badc" is false).
Reference solution
Python
def canBeEqual(s1: str, s2: str) -> bool:
def same(i: int, j: int) -> bool:
return (s1[i] == s2[i] and s1[j] == s2[j]) or (s1[i] == s2[j] and s1[j] == s2[i])
return same(0, 2) and same(1, 3)Java
public static boolean canBeEqual(String s1, String s2) {
return same(s1, s2, 0, 2) && same(s1, s2, 1, 3);
}
static boolean same(String a, String b, int i, int j) {
return (a.charAt(i) == b.charAt(i) && a.charAt(j) == b.charAt(j))
|| (a.charAt(i) == b.charAt(j) && a.charAt(j) == b.charAt(i));
}C++
bool canBeEqual(string s1, string s2) {
auto same = [&](int i, int j) {
return (s1[i] == s2[i] && s1[j] == s2[j]) || (s1[i] == s2[j] && s1[j] == s2[i]);
};
return same(0, 2) && same(1, 3);
}JavaScript
var canBeEqual = function(s1, s2) {
var same = function(i, j) {
return (s1[i] === s2[i] && s1[j] === s2[j]) || (s1[i] === s2[j] && s1[j] === s2[i]);
};
return same(0, 2) && same(1, 3);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings