Skip to main content
Talentd

K-Similar Strings - Solution & Explanation

HardStringBreadth-First Search10 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

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 <= 20
  • s2.length == s1.length
  • s1 and s2 contain only lowercase letters from the set {'a', 'b', 'c', 'd', 'e', 'f'}.
  • s2 is an anagram of s1.

Approach Overview

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.

Approach 1: Breadth-First Search (BFS) Approach

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor →

Approach 2: Greedy Depth-First Search (DFS) with Pruning

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

Code

C++C#

C++

C#

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(N!), for tracking the visited states (permutations) and BFS queue size.

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.
Space Complexity: O(N), due to the recursion depth used to maintain call stacks.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Breadth-First Search (BFS)O(n!) worst caseO(n!)When you want the clearest shortest-path formulation and guaranteed minimal swaps
Greedy DFS with PruningO(n!) worst caseO(n)When optimizing search using pruning and minimizing memory usage

Video Solution

Leetcode 854(Hard) K-Similar Strings: Simple C++ Solution • Shivam Patel • 4,165 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is K-Similar Strings easy or hard?
K-Similar Strings is classified as a Hard problem because it requires modeling the task as a graph search over permutations and applying pruning to keep the state space manageable. Understanding why only certain swaps should be explored is the key insight that makes the problem tractable.
How to solve K-Similar Strings in O(n)?
An O(n) solution is not possible because the problem requires exploring multiple swap combinations to guarantee the minimum transformation sequence. The standard approach uses BFS or DFS with pruning over string states. These algorithms explore permutations but reduce the search space by only fixing mismatched positions.
What is the best approach for K-Similar Strings?
The most common solution uses Breadth-First Search (BFS) on string states. Each state represents a string configuration, and swaps generate neighboring states. By always fixing the first mismatched index and only swapping with characters that match the target, the branching factor stays small. BFS guarantees the minimum number of swaps because it explores transformations level by level.
What data structure is used in K-Similar Strings?
The BFS solution relies on a queue to process string states level by level and a hash set to track visited permutations. These structures prevent repeated exploration and ensure the algorithm finds the shortest swap sequence. The DFS approach instead uses recursion with pruning conditions.
What is the time complexity of K-Similar Strings?
The worst-case time complexity is O(n!) because every permutation of the string could theoretically be explored. In practice, pruning strategies significantly reduce the search space. Most optimized implementations behave closer to O(n^3)–O(n^4) for typical constraints due to fixing mismatches greedily.
K-Similar Strings Python or Java solution approach?
Both Python and Java implementations typically use BFS with a queue and a visited set. At each step, find the first mismatched index and generate new strings by swapping with characters that match the target string at that position. This keeps the number of generated states manageable.
Is K-Similar Strings asked at Google, Amazon, or Meta?
K-Similar Strings is considered a hard interview problem and appears in advanced algorithm rounds at companies like Google and Meta. It tests knowledge of BFS state search, pruning techniques, and reasoning about permutations. Candidates are often expected to explain the mismatch-based pruning optimization.

Ready to solve this problem?

Practice K-Similar Strings with our built-in code editor and test cases.

Practice on FleetCode
Previous

Couples Holding Hands