854. K-Similar Strings

Problem Link

Description

---

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.

Solution

---

Python3

class Solution:
    def kSimilarity(self, s1: str, s2: str) -> int:
        N = len(s1)
        queue = deque([s1])
        level = 0
        visited = set([s1])
 
        while queue:
            n = len(queue)
            
            for _ in range(n):
                s = queue.popleft()
                
                if s == s2: return level
                
                s = list(s)
                
                i = 0
                while i < N and s[i] == s2[i]:
                    i += 1
 
                for j in range(i + 1, N):
                    if s[j] == s2[i]:
                        s[i], s[j] = s[j], s[i]
                        word = "".join(s)
                        if word not in visited:
                            visited.add(word)
                            queue.append(word)
                        s[i], s[j] = s[j], s[i]
                
            level += 1
        
        return -1