Check if Strings Can be Made Equal With Operations I solution and explanation
Google
9 more videos on this problem
Check if Strings Can be Made Equal With Operations I and II | 2 Approaches | Leetcode 2839 and 2840codestorywithMIK · 30:44 · 9K views
Leetcode BiWeekly contest 112 - Easy - Check if Strings Can be Made Equal With Operations IPrakhar Agrawal · 7:08 · 1K views
2839. Check if Strings Can be Made Equal With Operations I (Leetcode Easy)Programming Live with Larry · 3:55 · 392 views
2839. Check if Strings Can be Made Equal With Operations I | Leetcode Daily - PythonLeetcode Daily · 3:52 · 391 views
Check if Strings Can be Made Equal With Operations I | LeetCode 2839 | Java Code | Developer CoderDeveloper Coder · 7:47 · 187 views
Leetcode | 2839 Check if Strings Can be Made Equal With Operations I | Java | Simple TrickCakot Coding · 8:14 · 144 views
Check if Strings Can be Made Equal With Operations I | LeetCode 2839 - Pythonimpoldev · 5:57 · 139 views
leetcode 2839. Check if Strings Can be Made Equal With Operations I -comparisonCode-Yao · 6:34 · 116 views
Check if Strings Can be Made Equal With Operations I (LeetCode 2839)Algo Andre · 7:25 · 89 views
Verify Limited Permutations | Check if Strings Can be Made Equal With Operations I | LeetCode 2839Daily Dose Of LeetCode · 12:53 · 62 views
The 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
iandjsuch thatj - i = 2, 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 = "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:
Input: s1 = "abcd", s2 = "dacb" Output: false Explanation: It is not possible to make the two strings equal.
Constraints:
s1.length == s2.length == 4s1ands2consist only of lowercase English letters.
Approach overview
Problem Overview: You are given two strings s and t, each of length 4. The only allowed operations are swapping characters at indices (0,2) or (1,3) any number of times. The task is to determine whether these operations can transform s into t.
Approach 1: Position Pair Swap Analysis (O(1) time, O(1) space)
The allowed swaps divide the string into two independent groups of positions: (0,2) and (1,3). Any number of operations only rearranges characters inside these pairs. That means the characters at indices 0 and 2 can only swap with each other, and the same applies to indices 1 and 3. To verify if transformation is possible, compare the unordered character pairs from s and t for these positions. If the set of characters in s[0], s[2] matches t[0], t[2] and the set in s[1], s[3] matches t[1], t[3], the strings can be made equal. Since the string length is fixed at 4, this check runs in constant time with no additional memory.
Approach 2: Direct Character Position Swap Verification (O(1) time, O(1) space)
Another way is to simulate the constraints of the allowed swaps directly. Since each pair can only appear in two configurations (original or swapped), you check both possibilities for each pair. For indices (0,2), verify whether either s[0] == t[0] && s[2] == t[2] or s[0] == t[2] && s[2] == t[0]. Apply the same logic to indices (1,3). If both position groups match one of the valid configurations, the transformation is possible. This method avoids sorting or auxiliary structures and directly validates the only permutations reachable through the operations.
Both approaches rely on the same key insight: the operations do not allow arbitrary permutations of the string. They only swap characters within fixed index pairs. Recognizing these constrained swap groups simplifies the problem to constant-time checks rather than full permutation exploration. Problems like this often appear in string manipulation and simulation categories where understanding operation constraints eliminates brute-force search. The reasoning pattern also appears in some greedy style interview questions where local constraints determine global feasibility.
Recommended for interviews: The Position Pair Swap Analysis approach is what interviewers expect. It shows you quickly recognize that swaps form independent position groups and reduce the problem to comparing character pairs. The direct verification approach reaches the same result but demonstrates the reasoning more explicitly. Both run in constant time, but identifying the invariant swap groups is the key insight interviewers look for.
Approach 1: Position Pair Swap Analysis
To make the two strings equal, we can perform an operation in which any two characters at positions with an index difference of 2 can be swapped. For example, the available swaps for a string of four characters are between indices (0, 2) and (1, 3). Consider swapping character pairs: the first and third characters, and the second and fourth characters.
For the operation constraints, this means we essentially have two independent pairs of characters that can be freely swapped within themselves. Therefore, if the character set comprising these pairs in s1 equals s2, the operation is possible, otherwise, it is not.
def canBeEqual(s1: str, s2: str) -> bool:
return (s1[0] == s2[0] or s1[0] == s2[2]) and \
(s1[1] == s2[1] or s1[1] == s2[3]) and \
(s1[2] == s2[0] or s1[2] == s2[2]) and \
(s1[3] == s2[1] or s1[3] == s2[3])public class Solution {
public boolean canBeEqual(String s1, String s2) {
return (s1.charAt(0) == s2.charAt(0) || s1.charAt(0) == s2.charAt(2)) &&
(s1.charAt(1) == s2.charAt(1) || s1.charAt(1) == s2.charAt(3)) &&
(s1.charAt(2) == s2.charAt(0) || s1.charAt(2) == s2.charAt(2)) &&
(s1.charAt(3) == s2.charAt(1) || s1.charAt(3) == s2.charAt(3));
}
}#include <iostream>
#include <string>
bool canBeEqual(std::string s1, std::string s2) {
return (s1[0] == s2[0] || s1[0] == s2[2]) &&
(s1[1] == s2[1] || s1[1] == s2[3]) &&
(s1[2] == s2[0] || s1[2] == s2[2]) &&
(s1[3] == s2[1] || s1[3] == s2[3]);
}function canBeEqual(s1, s2) {
return (s1[0] == s2[0] || s1[0] == s2[2]) &&
(s1[1] == s2[1] || s1[1] == s2[3]) &&
(s1[2] == s2[0] || s1[2] == s2[2]) &&
(s1[3] == s2[1] || s1[3] == s2[3]);
}#include <stdbool.h>
#include <string.h>
bool canBeEqual(char * s1, char * s2) {
return (s1[0] == s2[0] || s1[0] == s2[2]) &&
(s1[1] == s2[1] || s1[1] == s2[3]) &&
(s1[2] == s2[0] || s1[2] == s2[2]) &&
(s1[3] == s2[1] || s1[3] == s2[3]);
}public class Solution {
public bool CanBeEqual(string s1, string s2) {
return (s1[0] == s2[0] || s1[0] == s2[2]) &&
(s1[1] == s2[1] || s1[1] == s2[3]) &&
(s1[2] == s2[0] || s1[2] == s2[2]) &&
(s1[3] == s2[1] || s1[3] == s2[3]);
}
}Pythonic verification checks are applied to ascertain if swapping within bounds allows alignment. This comprehensively checks all character swaps in constant time.
Time Complexity: O(1), owing to a fixed number of checks.
Space Complexity: O(1), does not rely on input-variable space.
Approach 2: Direct Character Position Swap Verification
This approach inspects possible direct swapping configurations. For any string of length 4, we focus on performing swaps and generating all possible rearrangements that adhere to the swap constraints. If any rearrangement of s1 matches s2, we return true, otherwise false.
def canBeEqual(s1: str, s2: str) -> bool:
return s1 == s2 or \
(s1[0] == s2[2] and s1[1] == s2[3] and \
s1[2] == s2[0] and s1[3] == s2[1])public class Solution {
public boolean canBeEqual(String s1, String s2) {
return (s1.equals(s2)) ||
(s1.charAt(0) == s2.charAt(2) && s1.charAt(1) == s2.charAt(3) &&
s1.charAt(2) == s2.charAt(0) && s1.charAt(3) == s2.charAt(1));
}
}#include <iostream>
#include <string>
bool canBeEqual(std::string s1, std::string s2) {
return (s1 == s2) ||
(s1[0] == s2[2] && s1[1] == s2[3] && s1[2] == s2[0] && s1[3] == s2[1]);
}function canBeEqual(s1, s2) {
return s1 === s2 ||
(s1[0] === s2[2] && s1[1] === s2[3] &&
s1[2] === s2[0] && s1[3] === s2[1]);
}#include <stdbool.h>
#include <string.h>
bool canBeEqual(char * s1, char * s2) {
return (s1[0] == s2[0] && s1[1] == s2[1] && s1[2] == s2[2] && s1[3] == s2[3]) ||
(s1[0] == s2[2] && s1[1] == s2[3] && s1[2] == s2[0] && s1[3] == s2[1]);
}public class Solution {
public bool CanBeEqual(string s1, string s2) {
return (s1.Equals(s2)) ||
(s1[0] == s2[2] && s1[1] == s2[3] &&
s1[2] == s2[0] && s1[3] == s2[1]);
}
}Direct and permutation-based equivalence checks through Python, aligns with 1st/3rd and 2nd/4th swaps.
Time Complexity: O(1), since its operations are fixed.
Space Complexity: O(1), minimal storage requirements.
Approach 3: Counting
We observe the operation in the problem, and find that if the parity of the two indices i and j of the string is the same, then their order can be changed by swapping.
Therefore, we can count the occurrence times of the characters at odd indices and even indices in the two strings. If the counting results of the two strings are the same, then we can make the two strings equal through the operation.
The time complexity is O(n + |\Sigma|), and the space complexity is O(|\Sigma|). Here, n is the length of the string, and \Sigma is the character set.
Similar problems:
function canBeEqual(s1: string, s2: string): boolean {
const cnt: number[][] = Array.from({ length: 2 }, () => Array.from({ length: 26 }, () => 0));
for (let i = 0; i < s1.length; ++i) {
++cnt[i & 1][s1.charCodeAt(i) - 97];
--cnt[i & 1][s2.charCodeAt(i) - 97];
}
return cnt.every(arr => arr.every(x => x === 0));
}func canBeEqual(s1 string, s2 string) bool {
cnt := [2][26]int{}
for i := 0; i < len(s1); i++ {
cnt[i&1][s1[i]-'a']++
cnt[i&1][s2[i]-'a']--
}
for i := 0; i < 26; i++ {
if cnt[0][i] != 0 || cnt[1][i] != 0 {
return false
}
}
return true
}impl Solution {
pub fn can_be_equal(s1: String, s2: String) -> bool {
let mut cnt: [[i32; 26]; 2] = [[0; 26]; 2];
let n = s1.len();
let s1 = s1.as_bytes();
let s2 = s2.as_bytes();
for i in 0..n {
let idx = (i & 1) as usize;
cnt[idx][(s1[i] - b'a') as usize] += 1;
cnt[idx][(s2[i] - b'a') as usize] -= 1;
}
cnt.iter().all(|row| row.iter().all(|&x| x == 0))
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Position Pair Swap Analysis | Time Complexity: O(1), owing to a fixed number of checks. Space Complexity: O(1), does not rely on input-variable space. |
| Direct Character Position Swap Verification | Time Complexity: O(1), since its operations are fixed. Space Complexity: O(1), minimal storage requirements. |
| Counting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Position Pair Swap Analysis | O(1) | O(1) | Best general solution when recognizing that swaps form independent index groups |
| Direct Character Position Swap Verification | O(1) | O(1) | Useful when explicitly validating the two possible arrangements per swap pair |
Frequently asked questions
Is Check if Strings Can be Made Equal With Operations I easy or hard?
Check if Strings Can be Made Equal With Operations I is classified as an Easy problem. The challenge is recognizing that the allowed swaps create two independent index groups, which reduces the problem to simple pair comparisons.
Check if Strings Can be Made Equal With Operations I Python/Java solution
In Python or Java, the typical solution compares character pairs (0,2) and (1,3) between the two strings. If each pair contains the same characters regardless of order, return true; otherwise return false. The implementation uses simple conditional checks and runs in O(1) time.
How to solve Check if Strings Can be Made Equal With Operations I in O(1)?
Group the indices based on the allowed swaps: (0,2) and (1,3). Check whether the characters in each pair of the first string match the characters in the same pair of the second string regardless of order. If both groups match, the strings can be made equal.
What is the best approach for Check if Strings Can be Made Equal With Operations I?
The best approach is Position Pair Swap Analysis. The allowed operations only swap indices (0,2) and (1,3), creating two independent position groups. If the characters within each pair match between the two strings regardless of order, the transformation is possible. This solution runs in O(1) time and O(1) space.
Is Check if Strings Can be Made Equal With Operations I asked at Google/Amazon/Meta?
Problems with constrained swap operations and string transformations appear frequently in coding interviews at companies like Google, Amazon, and Meta. While this exact question may vary, the underlying idea of recognizing swap invariants and position groups is a common interview pattern.
What data structure is used in Check if Strings Can be Made Equal With Operations I?
The problem mainly uses basic string manipulation. Most implementations rely on direct character comparison or small pair checks rather than complex data structures, keeping both time and space complexity constant.
What is the time complexity of Check if Strings Can be Made Equal With Operations I?
The optimal solution runs in O(1) time because the strings have a fixed length of 4 and only a constant number of comparisons are required. Space complexity is also O(1) since no extra data structures are needed.