Abstract / Summary

Check if one string can become another by moving characters in at most k steps considering the distance between positions.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 38% (70k+ submissions).

Typical patterns to solve this problem:

• Hash Table
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution.canConvertString method decides whether one string s can be transformed into another string t using at most k incremental character operations. Each operation increases a character by one position in the alphabet, wrapping from 'z' back to 'a'. The algorithm first validates that the two strings share the same length, then iterates through paired characters to compute the required shift for each position. A fixed-size array tracks how many times each distinct shift value has been used, accounting for the fact that the same shift cannot be applied in the same operation count without waiting for a full alphabet cycle. If any shift usage exceeds the allowed number of operations k, the method aborts early and returns False; otherwise it returns True after processing all character pairs.

Key Steps

Length Check

The method begins by confirming that s and t are of equal length. If they differ, conversion is impossible, and the function returns False immediately.

if len(s) != len(t):
    return False

Compute Shift per Position

A list named steps with 26 zeroes is created to store the cumulative operation count required for each possible shift (1 through 25). The loop iterates over the characters of s and t in parallel using zip. When the characters are identical, no work is needed and the loop proceeds to the next pair.

steps = [0] * 26
for one, two in zip(s, t):
    if one == two:
        continue

If the characters differ, their Unicode code points are obtained with ord. When the target character two precedes the source character one in the alphabet, a wrap-around is required; the code adds 26 to two to simulate moving forward through the alphabet.

one = ord(one)
two = ord(two)
if two < one:
    two += 26  # wraparound

The actual shift needed is the difference two - one. This value lies in the range 1-25.

shift = two - one

Record Shift Usage

The algorithm records how many operation slots are needed for each shift. The first time a particular shift appears, the required number of operations equals the shift itself. Subsequent occurrences of the same shift must wait an additional full alphabet cycle (26 steps) to avoid colliding with earlier uses.

if steps[shift] == 0:
    steps[shift] = shift          # first occurrence
else:
    steps[shift] += 26            # subsequent occurrence

Early Termination

After updating the usage count for a shift, the method checks whether the cumulative count exceeds the allowed limit k. If it does, conversion cannot be completed within the permitted number of operations, and the function returns False immediately.

if steps[shift] > k:
    return False

Final Result

If the loop finishes without triggering the early exit, all required shifts fit within the k operation budget, and the method returns True.

return True

Edge Cases Handled

When the two input strings have different lengths, the function rejects conversion outright, covering the case where a one-to-one mapping of characters is impossible. Identical characters at a given position generate no shift, and the loop skips any further processing for that pair, ensuring that unnecessary work is avoided. The wrap-around logic (if two < one: two += 26) correctly handles transitions such as 'z' to 'a', guaranteeing that the computed shift always reflects the forward distance in the cyclic alphabet. Situations where multiple positions require the same shift are managed by incrementally adding 26 to the stored count, effectively scheduling each occurrence in a later operation cycle. Finally, the early-exit condition (if steps[shift] > k) captures scenarios where the required number of operations for any shift surpasses the global limit k, preventing wasteful iteration over the remaining characters.

Performance Optimizations

The implementation uses a constant-size list of length 26 to store shift usage, providing O(1) random access without the overhead of a dictionary or hash map. By performing the length check before any other work, the method eliminates unnecessary computation for mismatched inputs. The use of ord to convert characters to integer code points enables fast arithmetic for shift calculation, avoiding slower string manipulation functions. The wrap-around adjustment adds 26 only when needed, sidestepping a modulo operation in the common case where the target character follows the source character alphabetically. The early termination check after each shift update prevents the algorithm from processing the entire string when the operation budget is already exceeded, reducing runtime for infeasible cases. Overall, the code processes each character pair exactly once, leveraging simple integer arithmetic and fixed-size data structures to achieve efficient execution.

Imagine you have two strings of letters, and each letter is like a bead on a spinning wheel shaped like a circle with twenty-six spots. To turn one letter into another, you have to move the wheel forward.

First, the code checks if the two strings are the same length. If they are not the same length, it is impossible for them to match, so it stops right away.

Then, it looks at every letter in both strings one by one to see how far the wheel needs to turn to make them match. Sometimes a letter might already be the same, so no turn is needed. If the letters are different, it calculates how many clicks it takes to get from the first letter to the second letter.

Because the wheel has twenty-six spots, you can keep spinning it around as many times as you like. However, there is a limit called k, which is the total amount of spinning power allowed. The first time the code finds a specific distance it needs to move, it saves that number. If it needs to move that same distance again later, it has to add twenty-six more clicks to the count because the wheel needs to spin all the way around again.

If at any point the number of clicks needed to get from one letter to the other is more than the limit k, the code declares that it is impossible to finish the mission.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java		Python			TS
	WalkCCC	C++	Java		Python
	leetcode.ca	C++	Java		Python		Go
	Progiez	C++	Java		Python
github	black-shadows	C++
	charles-wangkai		Java
	everthis			JS
	FelixFan1122		Java
	fsq	C++
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007				Python
	suxrobGM					C#
	varunu28		Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
FelixFan1122	Java
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
suxrobGM	C#
varunu28	Java
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality