Strings s1 and s2 are k-similar (for some non-negative integer k) if we can swap the positions of two letters in s1 exactly k times so that the resulting string equals s2.
Given two anagrams s1 and s2, return the smallest k for which s1 and s2 are k-similar.
Example 1:
Input: s1 = "ab", s2 = "ba" Output: 1 Explanation: The two string are 1-similar because we can use one swap to change s1 to s2: "ab" --> "ba".
Example 2:
Input: s1 = "abc", s2 = "bca" Output: 2 Explanation: The two strings are 2-similar because we can use two swaps to change s1 to s2: "abc" --> "bac" --> "bca".
Constraints:
1 <= s1.length <= 20s2.length == s1.lengths1 and s2 contain only lowercase letters from the set {'a', 'b', 'c', 'd', 'e', 'f'}.s2 is an anagram of s1.Problem Overview: You are given two anagram strings s1 and s2. A swap can exchange any two characters in s1. The goal is to compute the minimum number of swaps required to transform s1 into s2. Since both strings contain the same characters, the challenge is finding the smallest sequence of swaps that fixes mismatched positions.
Approach 1: Breadth-First Search (BFS) State Search (O(n!) time, O(n!) space)
This problem can be modeled as a shortest-path search where each string configuration is a node in a graph. Start from s1 and generate new states by swapping characters. A Breadth-First Search guarantees the first time you reach s2 uses the minimum number of swaps. To reduce branching, locate the first index where the current string differs from s2. Only swap that character with a later index that moves the correct target character into place. Each valid swap produces a new string state that gets pushed into a queue if it hasn't been visited. A visited set prevents revisiting permutations. This pruning drastically reduces the search space compared to exploring all possible swaps.
The key insight is that you should only fix the earliest mismatch instead of trying every swap pair. That greedy restriction turns a factorial search into a manageable BFS traversal. Each level of BFS represents one additional swap, so the level where s2 appears is the answer.
Approach 2: Greedy Depth-First Search (DFS) with Pruning (O(n!) worst-case time, O(n) recursion space)
A backtracking approach using Depth-First Search can also solve the problem efficiently with aggressive pruning. At each step, find the first mismatch between the current string and s2. Try swapping that character with positions later in the string that match the needed target character. After performing a swap, recursively continue fixing the remaining suffix. If the current swap count already exceeds the best solution found so far, prune that branch.
This greedy restriction ensures every swap immediately fixes at least one mismatch, preventing unnecessary permutations. Combined with pruning and early termination, the DFS approach often runs faster in practice because it avoids maintaining large BFS queues. The implementation relies heavily on efficient character swapping and careful backtracking.
Since the input is a string anagram pair, both approaches rely on the observation that optimal swaps always correct mismatched characters rather than introducing new mismatches.
Recommended for interviews: The BFS approach is the most common explanation in interviews because it clearly models the problem as a shortest transformation sequence. It demonstrates strong understanding of state-space search and pruning. The DFS with pruning solution is more optimized and often faster in practice, but BFS tends to be easier to reason about and prove correct during an interview discussion.
This approach uses a Breadth-First Search (BFS) strategy to find the shortest sequence of swaps to transform s1 into s2. The BFS strategy helps in systematically exploring all possible strings derived from swapping two characters in s1, while ensuring the shortest path (minimum number of swaps) is found first. We use a queue to keep track of the strings arising from swaps at each level, ensuring only valid and minimal swap sequences are explored.
This Python solution uses a deque from the collections module to facilitate the BFS approach. We start by defining a neighbors function that generates valid strings by swapping characters in s1 to match s2 at each differing position iteratively. We traverse the queue using BFS, updating and expanding our exploration by examining neighbors—strings that can be formed by one swap—of the current state. This guarantees finding the minimum swaps needed when we first encounter s2.
Time Complexity: O(N!), where N is the length of the string due to the factorial nature of permutation swaps.
Space Complexity: O(N!), for tracking the visited states (permutations) and BFS queue size.
In this approach, we use a Depth-First Search (DFS) strategy augmented with greedy techniques and pruning to find the minimal swaps quickly. By always attempting swaps that immediately match a mismatched character to its correct position in s2, the algorithm reduces unnecessary search paths significantly. Pruning eliminates evidently suboptimal paths early, allowing us to focus computational effort on promising candidates that move closer to the solution.
The C++ solution uses a recursive DFS enhanced by a greedy selection: when swapping characters, it prioritizes those that immediately resolve mismatches. The pruning occurs due to the minimum swaps tracking, which ensures only the most promising swaps are made (only those that better align s1 to s2).
Time Complexity: O(N!), where N is the length of the string as swaps might explore all possible permutations.
Space Complexity: O(N), due to the recursion depth used to maintain call stacks.
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) Approach | Time Complexity: O(N!), where N is the length of the string due to the factorial nature of permutation swaps. |
| Greedy Depth-First Search (DFS) with Pruning | Time Complexity: O(N!), where N is the length of the string as swaps might explore all possible permutations. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (BFS) | O(n!) worst case | O(n!) | When you want the clearest shortest-path formulation and guaranteed minimal swaps |
| Greedy DFS with Pruning | O(n!) worst case | O(n) | When optimizing search using pruning and minimizing memory usage |
Leetcode 854(Hard) K-Similar Strings: Simple C++ Solution • Shivam Patel • 4,110 views views
Watch 9 more video solutions →Practice K-Similar Strings with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor