0870HardHash TableStringBreadth-First Search

Fewest Swaps Between Two Blend Codes

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

Two blend codes s1 and s2 are the same length and use only the letters 'a' through 'f'. They are rearrangements of each other, so each letter appears the same number of times in both.

One swap exchanges the letters at two positions of s1. Return the fewest swaps that turn s1 into s2.

Examples

Example 1

Input: s1 = "abcd", s2 = "badc"
Output: 2

Swapping the first two letters gives "bacd", and swapping the last two gives "badc".

Example 2

Input: s1 = "abc", s2 = "bca"
Output: 2

Swapping the first two letters gives "bac", and swapping the last two gives "bca".

Example 3

Input: s1 = "abcdef", s2 = "abcdef"
Output: 0

The two codes already read the same, so no swap is needed.

Constraints

1 <= s1.length <= 20
s1.length == s2.length
s1 and s2 use only the letters a, b, c, d, e and f
s2 is a rearrangement of s1

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def fewest_code_swaps(s1: str, s2: str) -> int:

Java

public int fewestCodeSwaps(String s1, String s2)

The intended approach

Time O(states) in the worst case, but the restriction to useful swaps keeps the search small at the declared length of at most twenty letters.Space O(states) for the codes already reached.

Positions where the two codes already agree never need touching, so walk to the first disagreement and only ever swap a letter into it. Swapping in a letter that the target actually wants there is never worse than swapping in one it does not, so from that first disagreement only the positions holding the wanted letter are worth trying. Searching outward one swap at a time, with that restriction, reaches the target in the fewest swaps, and remembering the codes already reached keeps the search from going round in circles.

Pythonentry point: fewest_code_swaps

def fewest_code_swaps(s1, s2):
    if s1 == s2:
        return 0
    seen = {s1}
    frontier = [s1]
    steps = 0
    while frontier:
        steps += 1
        nxt = []
        for cur in frontier:
            # skip the positions that already agree
            i = 0
            while cur[i] == s2[i]:
                i += 1
            for j in range(i + 1, len(cur)):
                # only swap in a letter the target wants at position i
                if cur[j] != s2[i]:
                    continue
                chars = list(cur)
                chars[i], chars[j] = chars[j], chars[i]
                cand = "".join(chars)
                if cand == s2:
                    return steps
                if cand not in seen:
                    seen.add(cand)
                    nxt.append(cand)
        frontier = nxt
    return 0

The obvious version

Search outward one swap at a time trying every pair of positions, with no restriction on which swaps are worth making, until the target code turns up. Explores far more codes but assumes nothing about useful swaps.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_fewest_code_swaps(s1, s2):
    if s1 == s2:
        return 0
    seen = {s1}
    frontier = [s1]
    steps = 0
    while frontier:
        steps += 1
        nxt = []
        for cur in frontier:
            for a in range(len(cur)):
                for b in range(a + 1, len(cur)):
                    if cur[a] == cur[b]:
                        continue
                    chars = list(cur)
                    chars[a], chars[b] = chars[b], chars[a]
                    cand = "".join(chars)
                    if cand == s2:
                        return steps
                    if cand not in seen:
                        seen.add(cand)
                        nxt.append(cand)
        frontier = nxt
    return 0

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in