We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

K-Similar Strings

Number: 884

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given two anagrams s1 and s2, determine the smallest number of swaps needed to transform s1 into s2. A swap is defined as exchanging the positions of two letters in s1. The challenge is to compute the minimum number of such swaps (k) required so that s1 becomes identical to s2.

Key Insights

  • Both strings are anagrams, so they contain the same characters though possibly in different orders.
  • The problem can be modeled as a state-space search where each valid swap transforms the string closer to s2.
  • A Breadth-First Search (BFS) strategy guarantees finding the minimum number of swaps as it explores all transformations level-by-level.
  • Only swapping characters that instantly correct a discrepancy (i.e., matching the character in s2) helps prune the search space effectively.

Space and Time Complexity

Time Complexity: In the worst case the number of states explored is exponential in the length of the string. However, the pruning strategy (only swapping to correct positions) significantly reduces the average-case complexity. Space Complexity: O(V) where V is the number of unique string states generated, which is also exponential in the worst case.

Solution

The solution uses a BFS approach where each node represents a string state. Start from s1 and at every step:

  1. Find the first index where the current string differs from s2.
  2. For each subsequent index that can fix this mismatch (i.e., its character matches s2 at the mismatch index), generate a new state by swapping.
  3. Enqueue each new state if it has not been visited.
  4. Continue until s2 is reached, at which point the level (swap count) is the answer. This approach guarantees that the first time s2 is encountered, it has been reached with the minimum number of swaps.

Code Solutions

from collections import deque

def kSimilarity(s1: str, s2: str) -> int:
    # BFS queue: (current_string, current_swap_count)
    queue = deque([(s1, 0)])
    visited = {s1}
    
    while queue:
        current, swaps = queue.popleft()
        if current == s2:
            return swaps
        # Convert string to list for easy swap operations
        cur_list = list(current)
        # Find first index where current and target differ
        i = 0
        while i < len(cur_list) and cur_list[i] == s2[i]:
            i += 1
        # For all indices j where swapping helps fix the mismatch at index i
        for j in range(i + 1, len(cur_list)):
            # Only consider swaps that directly put the right character at index i
            if cur_list[j] == s2[i] and cur_list[j] != s2[j]:
                # Swap characters at positions i and j
                cur_list[i], cur_list[j] = cur_list[j], cur_list[i]
                new_state = "".join(cur_list)
                if new_state not in visited:
                    visited.add(new_state)
                    queue.append((new_state, swaps + 1))
                # Swap back for next iteration
                cur_list[i], cur_list[j] = cur_list[j], cur_list[i]
    return -1  # Should never reach here as s1 and s2 are anagrams

# Example usage:
print(kSimilarity("ab", "ba"))   # Output: 1
print(kSimilarity("abc", "bca")) # Output: 2
← Back to All Questions