Tejav
Sign in
#854

K-Similar Strings

Hard
Hash Table↗String↗Breadth-First Search↗Hash Map↗Array↗
LeetCode ↗

Approaches

💡

Intuition

Time UnknownSpace Unknown

The optimal solution uses a breadth-first search (BFS) approach to explore the minimum number of swaps needed to transform s1 into s2. By only considering necessary swaps and using a queue, we can efficiently find the answer without generating all possible states.

⚙️

Algorithm

5 steps
  1. 1Step 1: Initialize a queue for BFS and a set to track visited states.
  2. 2Step 2: Start with the initial string s1 and count of swaps as 0.
  3. 3Step 3: For each string in the queue, generate all possible swaps that lead to a valid state.
  4. 4Step 4: If we reach s2, return the count of swaps.
  5. 5Step 5: If the queue is empty and s2 hasn't been reached, return -1.
solution.py25 lines
1# Full working Python code
2from collections import deque
3
4class Solution:
5    def kSimilarity(self, s1: str, s2: str) -> int:
6        if s1 == s2:
7            return 0
8        queue = deque([(s1, 0)])
9        visited = set([s1])
10        while queue:
11            current, swaps = queue.popleft()
12            if current == s2:
13                return swaps
14            for i in range(len(current)):
15                if current[i] != s2[i]:
16                    for j in range(i + 1, len(current)):
17                        if current[j] == s2[i]:
18                            next_state = list(current)
19                            next_state[i], next_state[j] = next_state[j], next_state[i]
20                            next_state = ''.join(next_state)
21                            if next_state not in visited:
22                                visited.add(next_state)
23                                queue.append((next_state, swaps + 1))
24                    break
25        return -1

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.