String Transforms Into Another String

String Transforms Into Another String looks like a string problem but is really about a mapping — plus one clever counting argument about whether a spare letter exists.

The slow way first

You might try to simulate the renames, picking an order and applying them one letter at a time. But the ordering is fiddly — renaming a → c while c still means something else can clobber data — and brute forcing every order is hopeless. We need a rule that decides the answer directly.

The question to ask: what makes a transform impossible? Two things. First, a single letter cannot go to two different places. Second, even a clean mapping can be stuck in a cycle with no free letter to break it.

The idea: consistent mapping plus a spare letter

Walk both strings together. For each column, str1 has letter a and str2 has letter b. The letter a must map to exactly one target: if we already recorded a → something-else, the answer is False. Otherwise record a → b and continue.

If the whole scan is consistent, there is one last catch. A rename like a → b, b → a is a cycle; to perform it you rename a → z (a temporary), then b → a, then z → b. That needs a spare letter unused in str2. If str2 uses all 26 letters, no spare exists and a cycle cannot be broken — so a full permutation is only allowed when str1 == str2 already.

The key insight: consistency is necessary, and a spare letter is what makes any consistent mapping actually achievable.

Walk through it

Step through the animation. The pointer i scans the columns left to right. Each str1 letter records its target underneath. a and c repeat but always agree, b and c are new, so no conflict ever appears. At the end we count the distinct letters in str2 — only three — so a spare letter exists and the answer is True.

Pseudocode

if str1 equals str2:
    return True                       # already done, no work needed
make an empty map called "mapping"    # maps a str1 letter -> its target
for each column with letters a (str1) and b (str2):
    if a is already a key in mapping:
        if mapping[a] is not b:
            return False              # a must map to two letters -> impossible
    else:
        mapping[a] = b               # record the target for this letter
return (number of distinct letters in str2) < 26   # a spare letter exists?

The Python solution

def can_convert(str1, str2):
    if str1 == str2:
        return True
    mapping = {}
    for a, b in zip(str1, str2):
        if a in mapping:
            if mapping[a] != b:
                return False
        else:
            mapping[a] = b
    return len(set(str2)) < 26

• The early str1 == str2 check handles the only case where a full 26-letter permutation is allowed.
• mapping records each str1 letter → the target it must become.
• zip(str1, str2) walks both strings column by column.
• If a letter is already mapped and the new target disagrees, return False — a letter cannot split.
• The final line is the spare-letter check: if str2 uses fewer than 26 distinct letters, some letter is free to serve as a temporary for breaking cycles, so the transform is achievable.

Complexity

The mapping holds at most 26 entries and the set at most 26 letters, so the extra space is bounded by the alphabet — effectively O(1).

When this pattern shows up

Practice