Check if Strings Can be Made Equal With Operations I
EasyPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach models the problem as a graph traversal problem. Each possible string configuration is a node in the graph, and an edge exists between two nodes if one can be transformed into the other by a single valid swap operation. We can use a search algorithm like Breadth-First Search (BFS) to explore all reachable strings starting from s1 and see if s2 is among them.
Algorithm
- Initialize a queue for Breadth-First Search (BFS) and add the initial string
s1. - Initialize a
Setto store visited strings to avoid cycles and redundant processing, and adds1to it. - Loop while the queue is not empty:
- Dequeue a string,
current. - If
currentis equal tos2, a valid sequence of operations has been found, so returntrue. - Generate two potential next states from
current:next1: by swapping characters at indices 0 and 2.next2: by swapping characters at indices 1 and 3.
- For each generated state, if it has not been visited before, add it to the queue and the visited set.
- Dequeue a string,
- If the queue becomes empty and
s2has not been reached, it's impossible to make the strings equal, so returnfalse.
Walkthrough
We can treat this problem as finding a path from a start node (s1) to a target node (s2) in a state-space graph. The BFS algorithm is a perfect fit for finding if a path exists.
- We start with a queue containing just
s1. - We also use a
Setto keep track of strings we've already processed to prevent getting into infinite loops (though not possible here, it's good practice) and to avoid redundant work. - The algorithm proceeds by taking a string from the queue, generating all possible strings that can be formed from it in one step (by swapping indices 0 and 2, or 1 and 3), and adding these new strings to the queue if they haven't been visited yet.
- If at any point we generate or encounter
s2, we know it's possible to transforms1intos2, and we can immediately returntrue. - If the queue runs out of strings to process and we have not found
s2, it meanss2is unreachable, so we returnfalse.
import java.util.HashSet;import java.util.LinkedList;import java.util.Queue;import java.util.Set; class Solution { private String swap(String s, int i, int j) { char[] chars = s.toCharArray(); char temp = chars[i]; chars[i] = chars[j]; chars[j] = temp; return new String(chars); } public boolean canBeEqual(String s1, String s2) { if (s1.equals(s2)) { return true; } Queue<String> queue = new LinkedList<>(); Set<String> visited = new HashSet<>(); queue.add(s1); visited.add(s1); while (!queue.isEmpty()) { String current = queue.poll(); // Generate neighbors by applying the two possible swaps String neighbor1 = swap(current, 0, 2); if (neighbor1.equals(s2)) return true; if (!visited.contains(neighbor1)) { queue.add(neighbor1); visited.add(neighbor1); } String neighbor2 = swap(current, 1, 3); if (neighbor2.equals(s2)) return true; if (!visited.contains(neighbor2)) { queue.add(neighbor2); visited.add(neighbor2); } } return false; }}Complexity
Time
O(1). The number of states in our graph is constant. For each state, we do a constant amount of work (swaps, string creations, comparisons, hash set operations). Thus, the overall time complexity is constant.
Space
O(1). Since the string length is fixed at 4, the total number of reachable states is also a small constant (at most 4). Therefore, the space required for the queue and the set is constant.
Trade-offs
Pros
It is a very general method that can be applied to a wide range of state-space search problems.
It is guaranteed to find a solution if one exists.
Cons
This approach is overly complex for a problem with such a small and fixed state space.
It has higher constant factor overhead due to the use of a queue, a set, and repeated string manipulations (creation, hashing).
A more direct approach is to realize that from any given string s1, we can only generate a small, finite set of other strings. The operations partition the string's characters into two independent groups: those at even indices (0, 2) and those at odd indices (1, 3). Within each group, the two characters can either stay in place or be swapped. This results in at most 4 unique strings that can be formed from s1. We can simply generate all of them and check if s2 is one of them.
Algorithm
- Start with the original string
s1. - Check if
s1is already equal tos2. If yes, returntrue. - Generate a new string by swapping characters at indices 0 and 2 of
s1. Check if this new string equalss2. If yes, returntrue. - Generate another new string by swapping characters at indices 1 and 3 of the original
s1. Check if this equalss2. If yes, returntrue. - Finally, generate a string by performing both swaps (swap 0 and 2, then swap 1 and 3). Check if this equals
s2. If yes, returntrue. - If none of the above four possibilities match
s2, returnfalse.
Walkthrough
The core idea is that any string reachable from s1 must be one of four possibilities, based on whether we swap the even-indexed characters, the odd-indexed characters, both, or neither.
- No swaps: The string remains
s1. - Even swap only: Swap
s1[0]ands1[2]. - Odd swap only: Swap
s1[1]ands1[3]. - Both swaps: Swap
s1[0]withs1[2]ANDs1[1]withs1[3].
We can systematically check if s2 matches any of these four configurations of s1.
class Solution { public boolean canBeEqual(String s1, String s2) { // Case 1: s1 is already equal to s2 (no swaps) if (s1.equals(s2)) { return true; } char[] s1Chars = s1.toCharArray(); // Case 2: Swap even indices (0 and 2) char[] s1EvenSwapped = s1Chars.clone(); char temp = s1EvenSwapped[0]; s1EvenSwapped[0] = s1EvenSwapped[2]; s1EvenSwapped[2] = temp; if (new String(s1EvenSwapped).equals(s2)) { return true; } // Case 3: Swap odd indices (1 and 3) char[] s1OddSwapped = s1Chars.clone(); temp = s1OddSwapped[1]; s1OddSwapped[1] = s1OddSwapped[3]; s1OddSwapped[3] = temp; if (new String(s1OddSwapped).equals(s2)) { return true; } // Case 4: Swap both even and odd indices char[] s1BothSwapped = s1EvenSwapped.clone(); // Start from the even-swapped version temp = s1BothSwapped[1]; s1BothSwapped[1] = s1BothSwapped[3]; s1BothSwapped[3] = temp; if (new String(s1BothSwapped).equals(s2)) { return true; } return false; }}Complexity
Time
O(1). We perform a constant number of swaps, string creations, and comparisons. Since the string length is fixed at 4, all operations take constant time.
Space
O(1). We create a few character arrays of constant size (4), so the space usage is constant.
Trade-offs
Pros
Much simpler to implement and reason about than a full graph search.
Directly enumerates all possibilities, which is feasible for a small state space.
Cons
Involves creating new string or character array objects, which can be slightly less performant than direct memory access and comparison.
The logic can be a bit verbose, checking four distinct cases.
The most efficient approach is based on a key insight about the allowed operations. The swap operation j - i = 2 means we can only swap characters at indices (0, 2) and (1, 3). This effectively partitions the string's characters into two independent sets: {s[0], s[2]} and {s[1], s[3]}. For s1 to be transformable into s2, the multiset of characters at even positions in s1 must match the multiset of characters at even positions in s2. The same must hold true for the characters at odd positions.
Algorithm
- The problem can be solved by checking two independent conditions:
- The multiset of characters at even indices (0 and 2) in
s1must be the same as the multiset of characters at even indices ins2. - The multiset of characters at odd indices (1 and 3) in
s1must be the same as the multiset of characters at odd indices ins2.
- The multiset of characters at even indices (0 and 2) in
- To check the first condition, we verify if
(s1[0] == s2[0] AND s1[2] == s2[2])OR(s1[0] == s2[2] AND s1[2] == s2[0]). - To check the second condition, we verify if
(s1[1] == s2[1] AND s1[3] == s2[3])OR(s1[1] == s2[3] AND s1[3] == s2[1]). - The function returns
trueonly if both conditions are met, otherwise it returnsfalse.
Walkthrough
This method avoids any string creation or complex data structures. It directly compares the characters based on the logical partitioning of the string.
The characters at indices 0 and 2 form one group. The characters at indices 1 and 3 form another. A character can never move from an even index to an odd index or vice-versa.
Therefore, for s1 to be transformable into s2, two things must be true:
- The pair of characters
{s1[0], s1[2]}must be a permutation of the pair{s2[0], s2[2]}. - The pair of characters
{s1[1], s1[3]}must be a permutation of the pair{s2[1], s2[3]}.
We can check these two conditions with a simple boolean expression. For two pairs of characters {a, b} and {c, d} to be permutations of each other, it must be that either a=c and b=d, or a=d and b=c. We apply this logic to both the even-indexed and odd-indexed characters.
class Solution { public boolean canBeEqual(String s1, String s2) { // Check if the multiset of characters at even positions are the same. // This means (s1[0], s1[2]) is a permutation of (s2[0], s2[2]). boolean evenMatch = (s1.charAt(0) == s2.charAt(0) && s1.charAt(2) == s2.charAt(2)) || (s1.charAt(0) == s2.charAt(2) && s1.charAt(2) == s2.charAt(0)); // Check if the multiset of characters at odd positions are the same. // This means (s1[1], s1[3]) is a permutation of (s2[1], s2[3]). boolean oddMatch = (s1.charAt(1) == s2.charAt(1) && s1.charAt(3) == s2.charAt(3)) || (s1.charAt(1) == s2.charAt(3) && s1.charAt(3) == s2.charAt(1)); // Both conditions must be true. return evenMatch && oddMatch; }}Complexity
Time
O(1). The solution consists of a fixed number of character accesses and boolean operations, which is constant time.
Space
O(1). This approach uses no extra space that scales with input size. It only reads from the input strings.
Trade-offs
Pros
Extremely efficient in both time and space as it only involves a few character comparisons.
No new objects or data structures are created, leading to minimal overhead.
The code is clean, concise, and directly implements the core logic of the problem.
Cons
The solution is highly specific to the problem's constraints (string length 4, swap distance 2) and is not easily generalizable to different rules.
Solutions
Solution
class Solution {public boolean canBeEqual(String s1, String s2) { int[][] cnt = new int[2][26]; for (int i = 0; i < s1.length(); ++i) { ++cnt[i & 1][s1.charAt(i) - 'a']; --cnt[i & 1][s2.charAt(i) - 'a']; } for (int i = 0; i < 26; ++i) { if (cnt[0][i] != 0 || cnt[1][i] != 0) { return false; } } return true; }}class Solution {public: bool canBeEqual(string s1, string s2) { vector<vector<int>> cnt(2, vector<int>(26, 0)); for (int i = 0; i < s1.size(); ++i) { ++cnt[i & 1][s1[i] - 'a']; --cnt[i & 1][s2[i] - 'a']; } for (int i = 0; i < 26; ++i) { if (cnt[0][i] || cnt[1][i]) { return false; } } return true; }};class Solution: def canBeEqual(self, s1: str, s2: str) -> bool: return sorted( s1[:: 2]) == sorted(s2[:: 2]) and sorted(s1[1:: 2]) == sorted(s2[1:: 2])Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.