# Solving Leetcode Interviews in Seconds with AI: K-Similar Strings


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "854" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

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

	# Explanation
	Here's the solution to find the smallest k for k-similar strings:

*   **BFS Approach:** Use Breadth-First Search (BFS) to explore possible swap sequences. The starting state is `s1`, and the target state is `s2`. The number of swaps represents the level in BFS.

*   **Optimization with Visited Set:** Avoid revisiting the same string states by keeping track of visited strings. This prevents infinite loops and redundant calculations.

*   **Efficient Swap Generation:**  For each string, find the first position where `s1[i] != s2[i]`. Then, iterate from `i + 1` to find a position `j` where `s1[j] == s2[i]`. Swapping `s1[i]` and `s1[j]` results in a new candidate string.

*   **Runtime Complexity:** O((N!)), where N is the length of the strings. Although strings are limited to length 20, this is the worst-case complexity of BFS.
    **Storage Complexity:** O(N!), due to the visited set.

	
	# Code
	```python
	from collections import deque

def kSimilarity(s1: str, s2: str) -> int:
    """
    Finds the smallest k for which s1 and s2 are k-similar.
    """

    if s1 == s2:
        return 0

    q = deque([(s1, 0)])  # (string, swaps)
    visited = {s1}
    n = len(s1)

    while q:
        curr_s, swaps = q.popleft()

        i = 0
        while curr_s[i] == s2[i]:
            i += 1

        for j in range(i + 1, n):
            if curr_s[j] == s2[i] and curr_s[j] != s2[j]:
                new_s = list(curr_s)
                new_s[i], new_s[j] = new_s[j], new_s[i]
                new_s = "".join(new_s)

                if new_s == s2:
                    return swaps + 1

                if new_s not in visited:
                    visited.add(new_s)
                    q.append((new_s, swaps + 1))

    return -1  # Should not reach here as s1 and s2 are anagrams
	```