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).
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; }}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.