K-Similar Strings - Practice Coding Problems

K-Similar Strings - Problem

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.

Input & Output

Example 1 — Basic Swap

$ Input: s1 = "ab", s2 = "ba"

› Output: 1

💡 Note: Swap s1[0] and s1[1]: "ab" → "ba". One swap needed.

Example 2 — No Swaps Needed

$ Input: s1 = "abc", s2 = "abc"

› Output: 0

💡 Note: Strings are already identical, no swaps needed.

Example 3 — Multiple Swaps

$ Input: s1 = "abcd", s2 = "cdab"

› Output: 2

💡 Note: First swap(0,2): "abcd" → "cbad", then swap(1,3): "cbad" → "cdab".

Constraints

1 ≤ s1.length ≤ 20
s2.length == s1.length
s1 and s2 contain only lowercase English letters
s1 and s2 are anagrams of each other

Visualization

Tap to expand

Understanding the Visualization

Input

Two anagram strings s1 and s2

Process

Find minimum character swaps needed

Output

Return smallest number k

Key Takeaway

🎯 Key Insight: Use BFS to explore string transformations level by level, ensuring minimum swaps are found first

Asked in

G Google 45 f Facebook 32 a Amazon 28

The key insight is to use BFS to explore string states level by level, guaranteeing minimum swaps. The optimized approach only considers swaps that fix incorrect positions. Best approach is Optimized BFS with Time: O(n! × n), Space: O(n!).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Backtracking	O(n!)	O(n)	Try all possible sequences of swaps using recursive backtracking
BFS - Breadth-First Search	O(n! × n²)	O(n!)	Use BFS to find minimum swaps by exploring states level by level
Optimized BFS with Early Pruning	O(n! × n)	O(n!)	BFS with optimization to only swap positions that need fixing

Brute Force with Backtracking — Algorithm Steps

Step 1: If strings are equal, return current swap count
Step 2: Try all possible swaps at current position
Step 3: Recursively solve for each swap option
Step 4: Return minimum swaps found

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Start with s1, target is s2

Try Swaps

Recursively try all possible swaps

Backtrack

Undo swaps and try other options

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <limits.h>

int minSwaps = INT_MAX;

void swap(char* a, char* b) {
    char temp = *a;
    *a = *b;
    *b = temp;
}

int backtrack(char* curr, const char* target, int swaps, int len) {
    if (strcmp(curr, target) == 0) {
        if (swaps < minSwaps) {
            minSwaps = swaps;
        }
        return swaps;
    }
    if (swaps >= minSwaps) {
        return INT_MAX;
    }
    
    int result = INT_MAX;
    
    for (int i = 0; i < len; i++) {
        if (curr[i] == target[i]) continue;
        for (int j = i + 1; j < len; j++) {
            if (curr[j] == target[i]) {
                // Try this swap
                swap(&curr[i], &curr[j]);
                int nextResult = backtrack(curr, target, swaps + 1, len);
                if (nextResult < result) {
                    result = nextResult;
                }
                // Backtrack
                swap(&curr[i], &curr[j]);
            }
        }
    }
    
    return result;
}

int solution(char* s1, char* s2) {
    minSwaps = INT_MAX;
    int len = strlen(s1);
    char temp[21];
    strcpy(temp, s1);
    int result = backtrack(temp, s2, 0, len);
    return result == INT_MAX ? 0 : result;
}

int main() {
    char s1[21], s2[21];
    fgets(s1, sizeof(s1), stdin);
    fgets(s2, sizeof(s2), stdin);
    s1[strcspn(s1, "\n")] = 0;
    s2[strcspn(s2, "\n")] = 0;
    int result = solution(s1, s2);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n!)

In worst case, tries all possible permutations of swaps

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth up to n levels

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~35 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler