K-Similar Strings
HardPrompt
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.lengths1ands2contain only lowercase letters from the set{'a', 'b', 'c', 'd', 'e', 'f'}.s2is an anagram ofs1.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach models the problem as finding the shortest path in a state space graph. Each unique permutation of the string s1 is a node, and a single swap operation between two strings constitutes an edge. We are looking for the minimum number of edges (swaps) to get from s1 to s2. Breadth-First Search (BFS) is the standard algorithm for this task. However, this brute-force method explores every possible swap at every step, leading to a combinatorial explosion of states.
Algorithm
- Model the problem as a shortest path problem on a graph.
- The nodes of the graph are all possible string permutations that can be formed from
s1. - An edge exists between two string nodes if one can be transformed into the other with a single swap.
- The goal is to find the shortest path from node
s1to nodes2. - Use Breadth-First Search (BFS) to find this shortest path, as BFS is guaranteed to find the shortest path in an unweighted graph.
- Start a BFS from
s1. In each step, generate all possible strings that can be obtained by swapping any two characters. - Use a
Setto keep track of visited strings to avoid cycles and redundant computations. - The level of the BFS at which
s2is found is the minimum number of swaps,k.
Walkthrough
The algorithm starts with a queue containing the initial string s1 and a set to store visited strings. It proceeds in levels, where each level corresponds to an additional swap. In each level, it dequeues all strings, and for each string, it generates all possible next strings by swapping every pair of characters. If a new, unvisited string is generated, it's added to the queue and the visited set. The search continues until the target string s2 is found. The number of levels traversed gives the smallest k.
While correct, this approach is not feasible. For a string of length N, there can be up to N! permutations. For each permutation, we can generate N*(N-1)/2 new strings. The complexity is prohibitive.
For example, the neighbor generation loop would look like this:
char[] currentChars = currentStr.toCharArray();for (int i = 0; i < currentStr.length(); i++) { for (int j = i + 1; j < currentStr.length(); j++) { if (currentChars[i] != currentChars[j]) { swap(currentChars, i, j); String nextStr = new String(currentChars); if (!visited.contains(nextStr)) { visited.add(nextStr); queue.add(nextStr); } swap(currentChars, i, j); // Backtrack } }}Complexity
Time
O(N! * N^2) in the worst case. We might visit all `N!` permutations, and for each, we spend `O(N^2)` time to generate neighbors.
Space
O(N! * N) in the worst case, to store all possible permutations in the visited set and queue. `N` is the length of the string.
Trade-offs
Pros
Conceptually simple and easy to understand.
Guaranteed to find the optimal solution (the smallest
k).
Cons
Extremely inefficient due to the massive state space.
The number of permutations is
N!, and for each state, we generateO(N^2)neighbors.Will result in a 'Time Limit Exceeded' error for the given constraints (
Nup to 20).
We can significantly improve the brute-force BFS by being more intelligent about the swaps we explore. Instead of trying every possible swap, we only consider swaps that make concrete progress towards the target string s2. We identify the first position where the current string differs from s2 and then only perform swaps that fix this specific position. This drastically prunes the search tree, making the BFS feasible for the given constraints.
Algorithm
- This approach is an optimization of the brute-force BFS.
- The core idea is to reduce the branching factor of the search by only making 'useful' swaps.
- Start a BFS from
s1. - For any string
current_sbeing processed, find the first indexiwherecurrent_s[i]does not matchs2[i]. - A 'useful' swap is one that places the correct character,
s2[i], into this positioni. - To do this, find all indices
j > iwherecurrent_s[j] == s2[i]. - For each such
j, generate a new string by swapping the characters atiandj. - Add these newly generated strings to the BFS queue if they haven't been visited before.
- The number of levels in the BFS until
s2is found is the answer.
Walkthrough
We use a standard BFS setup with a queue and a visited set. For each string currentStr we pull from the queue, we first find the first index i where currentStr.charAt(i) != s2.charAt(i). Since s1 and s2 are anagrams, the character s2.charAt(i) must exist somewhere in currentStr. We then iterate from j = i + 1 to the end of the string, looking for occurrences of s2.charAt(i). Each time we find currentStr.charAt(j) == s2.charAt(i), we perform the swap between i and j, create a nextStr, and if it's unvisited, add it to our queue and visited set. This ensures that every move makes direct progress, and since BFS explores level by level, we are guaranteed to find the path with the minimum number of swaps.
import java.util.HashSet;import java.util.LinkedList;import java.util.Queue;import java.util.Set; class Solution { public int kSimilarity(String s1, String s2) { if (s1.equals(s2)) { return 0; } Queue<String> queue = new LinkedList<>(); Set<String> visited = new HashSet<>(); queue.add(s1); visited.add(s1); int k = 0; while (!queue.isEmpty()) { int levelSize = queue.size(); for (int i = 0; i < levelSize; i++) { String currentStr = queue.poll(); if (currentStr.equals(s2)) { return k; } int firstMismatchIdx = 0; while (firstMismatchIdx < currentStr.length() && currentStr.charAt(firstMismatchIdx) == s2.charAt(firstMismatchIdx)) { firstMismatchIdx++; } char[] currentChars = currentStr.toCharArray(); for (int j = firstMismatchIdx + 1; j < currentStr.length(); j++) { if (currentChars[j] == s2.charAt(firstMismatchIdx) && currentChars[j] != currentChars[firstMismatchIdx]) { swap(currentChars, firstMismatchIdx, j); String nextStr = new String(currentChars); if (!visited.contains(nextStr)) { visited.add(nextStr); queue.add(nextStr); } swap(currentChars, firstMismatchIdx, j); // backtrack swap } } } k++; } return -1; // Should not be reached } private void swap(char[] chars, int i, int j) { char temp = chars[i]; chars[i] = chars[j]; chars[j] = temp; }}Complexity
Time
Hard to determine precisely, but it's related to `O(S * N * B)` where `S` is the number of states visited, `N` is for string operations, and `B` is the branching factor (at most `N-1`). It's significantly better than the brute-force approach.
Space
O(S * N), where `S` is the number of states visited and `N` is the string length. This is much smaller than `N!` but can still be large.
Trade-offs
Pros
Much more efficient than the brute-force approach due to a significantly smaller search space.
Guaranteed to find the optimal solution.
It is a practical and common solution for this type of problem.
Cons
The worst-case time complexity can still be exponential.
Memory usage can be high if a large number of states need to be stored in the visited set and queue.
The A* search algorithm is a powerful optimization over BFS for shortest path problems. By incorporating a heuristic function, it intelligently guides the search towards the goal. Instead of exploring all paths of a certain length equally (like BFS), A* prioritizes paths that are not only short but also appear to be getting closer to the target. This often leads to exploring far fewer states than a simple pruned BFS, making it the most efficient search-based approach for this problem.
Algorithm
- This approach enhances the pruned search by using a heuristic to prioritize more promising paths, which is the core idea of the A* search algorithm.
- The search uses a priority queue instead of a regular queue.
- The priority of a state (string) is determined by
f(s) = g(s) + h(s).g(s)is the actual cost (number of swaps) from the start strings1to the current strings.h(s)is a heuristic estimate of the cost fromsto the targets2.
- An effective and admissible heuristic
h(s)isceil(number of mismatched positions / 2). This is admissible because one swap can fix at most two mismatched positions. - The neighbor generation logic is the same as in the Pruned BFS approach.
- The algorithm terminates when it extracts
s2from the priority queue, returning the associatedg(s2)value.
Walkthrough
We use a priority queue to store states, where each state contains the string, the number of swaps so far (g), and its heuristic value (h). The priority queue sorts states based on g + h. We also use a map to keep track of the minimum swaps found to reach any string, to avoid redundant explorations.
The heuristic function, h(s), calculates the number of positions where s and s2 have different characters, let's call this mismatches. The estimated swaps needed is (mismatches + 1) / 2 (integer division for ceil).
The main loop extracts the state with the lowest g + h from the priority queue. If it's the target s2, we're done. Otherwise, we generate its neighbors using the same pruning strategy as before (fixing the first mismatch). For each neighbor, we calculate its new g and h values and add it to the priority queue if we've found a shorter path to it.
import java.util.HashMap;import java.util.Map;import java.util.PriorityQueue; class Solution { class State implements Comparable<State> { String str; int g_cost; // swaps so far int h_cost; // heuristic estimate State(String str, int g, String target) { this.str = str; this.g_cost = g; this.h_cost = calculateHeuristic(str, target); } private int calculateHeuristic(String s1, String s2) { int mismatches = 0; for (int i = 0; i < s1.length(); i++) { if (s1.charAt(i) != s2.charAt(i)) { mismatches++; } } return (mismatches + 1) / 2; } @Override public int compareTo(State other) { return (this.g_cost + this.h_cost) - (other.g_cost + other.h_cost); } } public int kSimilarity(String s1, String s2) { if (s1.equals(s2)) return 0; PriorityQueue<State> pq = new PriorityQueue<>(); Map<String, Integer> minSwaps = new HashMap<>(); pq.add(new State(s1, 0, s2)); minSwaps.put(s1, 0); while (!pq.isEmpty()) { State current = pq.poll(); if (current.g_cost > minSwaps.getOrDefault(current.str, Integer.MAX_VALUE)) { continue; } if (current.str.equals(s2)) { return current.g_cost; } int i = 0; while (current.str.charAt(i) == s2.charAt(i)) i++; char[] chars = current.str.toCharArray(); for (int j = i + 1; j < chars.length; j++) { if (chars[j] == s2.charAt(i) && chars[j] != chars[i]) { swap(chars, i, j); String nextStr = new String(chars); int newSwaps = current.g_cost + 1; if (newSwaps < minSwaps.getOrDefault(nextStr, Integer.MAX_VALUE)) { minSwaps.put(nextStr, newSwaps); pq.add(new State(nextStr, newSwaps, s2)); } swap(chars, i, j); // backtrack } } } return -1; // Should not be reached } private void swap(char[] arr, int i, int j) { char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }}Complexity
Time
Worst-case complexity is similar to BFS, but the average-case performance is much better and depends on the heuristic's quality. It's difficult to give a tight bound.
Space
O(S * N), where `S` is the number of states visited. A* aims to make `S` as small as possible.
Trade-offs
Pros
Generally the most efficient approach among search-based methods.
Significantly reduces the number of states explored compared to BFS by prioritizing promising paths.
Guaranteed to find the optimal solution because the heuristic is admissible.
Cons
Slightly more complex to implement than a standard BFS due to the priority queue and heuristic calculation.
The performance gain depends heavily on the quality of the heuristic.
Solutions
Solution
class Solution {public int kSimilarity(String s1, String s2) { Deque<String> q = new ArrayDeque<>(); Set<String> vis = new HashSet<>(); q.offer(s1); vis.add(s1); int ans = 0; while (true) { for (int i = q.size(); i > 0; --i) { String s = q.pollFirst(); if (s.equals(s2)) { return ans; } for (String nxt : next(s, s2)) { if (!vis.contains(nxt)) { vis.add(nxt); q.offer(nxt); } } } ++ans; } }private List<String> next(String s, String s2) { int i = 0, n = s.length(); char[] cs = s.toCharArray(); for (; cs[i] == s2.charAt(i); ++i) { } List<String> res = new ArrayList<>(); for (int j = i + 1; j < n; ++j) { if (cs[j] == s2.charAt(i) && cs[j] != s2.charAt(j)) { swap(cs, i, j); res.add(new String(cs)); swap(cs, i, j); } } return res; }private void swap(char[] cs, int i, int j) { char t = cs[i]; cs[i] = cs[j]; cs[j] = t; }}class Solution {public: int kSimilarity(string s1, string s2) { queue<string> q{{s1}}; unordered_set<string> vis{{s1}}; int ans = 0; while (1) { for (int i = q.size(); i; --i) { auto s = q.front(); q.pop(); if (s == s2) { return ans; } for (auto &nxt : next(s, s2)) { if (!vis.count(nxt)) { vis.insert(nxt); q.push(nxt); } } } ++ans; } } vector<string> next(string &s, string &s2) { int i = 0, n = s.size(); for (; s[i] == s2[i]; ++i) { } vector<string> res; for (int j = i + 1; j < n; ++j) { if (s[j] == s2[i] && s[j] != s2[j]) { swap(s[i], s[j]); res.push_back(s); swap(s[i], s[j]); } } return res; }};class Solution: def kSimilarity(self, s1: str, s2: str) -> int: def next(s): i = 0 while s[i] == s2[i]: i += 1 res = [] for j in range(i + 1, n): if s[j] == s2[i] and s[j] != s2[j]: res . append(s2[: i + 1] + s[i + 1: j] + s[i] + s[j + 1:]) return res q = deque([s1]) vis = {s1} ans, n = 0, len(s1) while 1: for _ in range(len(q)): s = q . popleft() if s == s2: return ans for nxt in next(s): if nxt not in vis: vis . add(nxt) q . append(nxt) ans += 1Video 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.