K Similar Strings - Leetcode Solution

Problem:

Given two strings A and B of equal length, and a list of k similar index pairs, find out if A and B are similar.

A string is said to be similar to another string if you can swap any two indices (i.e. characters) in the first string and get the second string.

Code:

Here is the Python code for the K Similar Strings problem on LeetCode. The time complexity of this code is O(n^2*k), where n is the length of the strings A and B.

from collections import deque

def kSimilarity(A: str, B: str, k: int) -> int:
    queue = deque([(A, 0)])
    visited = set([A])
    while queue:
        current_string, swaps = queue.popleft()
        if current_string == B:
            return swaps
        similar_positions = get_similar_positions(current_string, B)
        for pos1, pos2 in similar_positions:
            next_string = swap(current_string, pos1, pos2)
            if next_string not in visited:
                visited.add(next_string)
                queue.append((next_string, swaps+1))
    return -1
    

# Helper function to find similar (mismatched) positions between two  strings
def get_similar_positions(string1: str, string2: str) -> list:
    similar_positions = []
    for i in range(len(string1)):
        if string1[i] == string2[i]:
            continue
        for j in range(i+1, len(string1)):
            if string1[j] == string2[i] and string1[i] == string2[j]:
                similar_positions.append((i,j))
                break
    return similar_positions

# Helper function to swap two positions in a string
def swap(string: str, i: int, j: int) -> str:
    string_list = list(string)
    string_list[i], string_list[j] = string_list[j], string_list[i]
    return ''.join(string_list)

Explanation:

In this problem, we need to find out if A and B are similar, given a list of k similar index pairs. We can use BFS to solve this problem. We start by adding the initial string A to a queue and set it as visited. We then dequeue the string and generate all possible strings by swapping any two indices (characters). We add only the unvisited similar strings to the queue along with the number of swaps made to reach that string.

We continue this process until we reach string B in the queue. When we reach B, we return the number of swaps made to get to this string. If we exhaust all possible strings and still haven't found B, we return -1 to indicate that B cannot be obtained from A by making k swaps.

To generate all possible similar strings, we first need to find the similar positions between A and B. We iterate over the indices of the strings and check if they mismatch. If they do, we check the remaining characters in both the strings to find if they have similar characters. If they do, we swap the characters at those positions, and add the new string to the queue. We continue this process until we reach B.

The time complexity of this code is O(n^2k), where n is the length of the strings A and B. The space complexity is O(nk), since we store all possible strings in the queue.

1