Check if Strings Can be Made Equal With Operations I - Solution & Explanation
Problem Statement
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.
The solution in C checks if characters from the same positions in either string, or permuted according to the defined operations, can be re-arranged to match each character of the other string.
Complexity
Time Complexity: O(1), since the check involves a constant number of operations.
Space Complexity: O(1), since no additional space proportional to input size is required.
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.
This solution checks if a swap in the 1st and 3rd, and 2nd and 4th characters results in a match.
Complexity
Time Complexity: O(1), direct string comparison with simple permutations.
Space Complexity: O(1), no space allocation dependent on input.
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:
Complexity Comparison
| Approach | Complexity |
|---|---|
| Position Pair Swap Analysis | Time Complexity: O(1), since the check involves a constant number of operations. Space Complexity: O(1), since no additional space proportional to input size is required. |
| Direct Character Position Swap Verification | Time Complexity: O(1), direct string comparison with simple permutations. Space Complexity: O(1), no space allocation dependent on input. |
| Counting | — |
Detailed 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 |
Video Solution
Check if Strings Can be Made Equal With Operations I and II | 2 Approaches | Leetcode 2839 and 2840 • codestorywithMIK • 9,161 views views
Watch 9 more video solutions →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 Python/Java solution
How to solve Check if Strings Can be Made Equal With Operations I in O(1)?
What is the best approach for Check if Strings Can be Made Equal With Operations I?
Is Check if Strings Can be Made Equal With Operations I asked at Google/Amazon/Meta?
What data structure is used in Check if Strings Can be Made Equal With Operations I?
What is the time complexity of Check if Strings Can be Made Equal With Operations I?
Ready to solve this problem?
Practice Check if Strings Can be Made Equal With Operations I with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor