Can Convert String in K Moves: Shift Counting Pattern

You are given two strings s and t of equal length, and an integer k. In the ith move (1-indexed), you can shift any character of s by i positions forward in the circular alphabet (so z wraps back to a). Determine whether you can convert s into t using at most k moves. Each move number can only be used once.

This is LeetCode 1540: Can Convert String in K Moves, and it is a great exercise in modular arithmetic and resource allocation. The technique it teaches, assigning limited resources (move numbers) to competing requirements (character shifts), appears in scheduling and assignment problems throughout competitive programming.

Why this problem matters

At first glance, this problem seems like it might require simulation or backtracking. But it boils down to a clean counting argument. You need to figure out how many times each shift value appears and whether you have enough distinct move numbers in the range [1, k] to cover all of them.

This teaches you two transferable skills. First, circular character arithmetic using modulo 26. Second, the pattern of assigning unique resources to identical requirements, where the first occurrence is cheap and later occurrences cost more. You will see this same structure in problems involving task scheduling, frequency allocation, and greedy assignment.

The key insight

For each position i where s[i] differs from t[i], you need to shift s[i] forward by some amount d to reach t[i]. That amount is (ord(t[i]) - ord(s[i])) % 26. If d is 0, the characters already match and no move is needed.

Here is the critical observation: move number d shifts a character by exactly d positions. But move number d + 26 also shifts by d positions (since the alphabet is circular and 26 wraps around). Similarly, move d + 52 gives the same shift, and so on.

So if you have two positions that both need shift d, the first one uses move d, and the second uses move d + 26. A third would use d + 52. In general, the jth occurrence of shift d (0-indexed) uses move number d + 26 * j.

The answer is true if and only if every assigned move number is at most k.

The solution

def can_convert_string(s: str, t: str, k: int) -> bool:
    if len(s) != len(t):
        return False

    shift_count = [0] * 26

    for sc, tc in zip(s, t):
        diff = (ord(tc) - ord(sc)) % 26
        if diff == 0:
            continue
        move_needed = diff + 26 * shift_count[diff]
        if move_needed > k:
            return False
        shift_count[diff] += 1

    return True

Let's walk through what each piece does.

The shift_count array has 26 entries, one for each possible nonzero shift value (1 through 25, with index 0 unused). It tracks how many times each shift value has been seen so far.

For each pair of characters (sc, tc), you compute the circular distance diff. If diff is 0, the characters already match and you skip the position entirely. Otherwise, you calculate the move number this occurrence would need: diff + 26 * shift_count[diff]. This is because the first time you see shift diff, you use move diff. The second time, you use move diff + 26. The third time, diff + 52, and so on.

If the required move number exceeds k, you immediately return False, since you cannot perform that move. Otherwise, you increment the count for that shift value and continue.

If you make it through every position without exceeding k, the conversion is possible.

Visual walkthrough

Let's trace through the example s = "abcde", t = "bcefa", k = 28 step by step. Watch how duplicate shifts get assigned progressively larger move numbers.

The maximum move number assigned is 28, which fits within k = 28. So the answer is true. If k were 27, the second occurrence of shift 2 would need move 28, which would exceed k, and the answer would be false.

Complexity analysis

Time is O(n) where n is the length of the strings. You iterate through each character pair once, doing constant work per pair.

Space is O(1). The shift_count array always has exactly 26 entries regardless of input size. This is a fixed constant, so the space complexity is O(26) = O(1).

The building blocks

1. Circular shift computation

The pattern of computing the forward distance between two characters in a circular alphabet:

diff = (ord(tc) - ord(sc)) % 26

This gives you the number of forward steps from sc to tc wrapping around z to a. For example, from x to b the difference is (98 - 120) % 26 = (-22) % 26 = 4. You can verify: x, y, z, a, b is four steps. This modular distance pattern shows up in any problem involving circular structures, from clock arithmetic to circular buffer indexing.

2. Move number assignment for duplicate shifts

The pattern of assigning progressively larger resource IDs when the same requirement appears multiple times:

move_needed = diff + 26 * shift_count[diff]
shift_count[diff] += 1

The first occurrence of shift d gets move d. The second gets d + 26. The third gets d + 52. This is a greedy assignment: each new occurrence takes the smallest available move that produces the required shift. The pattern generalizes to any problem where identical requirements compete for distinct resources at regular intervals.

Edge cases

Before submitting, think through these scenarios:

• Strings already equal: every shift is 0, no moves needed. Return true regardless of k.
• Unequal lengths: if len(s) != len(t), return false immediately. You cannot add or remove characters.
• k smaller than the largest single shift: if any position needs shift d and k is less than d, return false.
• Many positions needing the same shift: if shift 1 appears 3 times, you need moves 1, 27, and 53. Check that 53 fits within k.
• All 25 nonzero shifts appear once: the largest move needed is 25. Return true if k is at least 25.
• Single character strings: if s and t are length 1, only one shift is needed. Check if it fits within k.

From understanding to recall

You have seen how to count shift values, assign move numbers using the d + 26 * count formula, and check the result against k. The logic is clean and the code is short. But reproducing it under pressure is a different challenge.

The details that trip people up are the modular arithmetic, remembering to skip positions where the shift is 0, and getting the move number formula right. These are not conceptual gaps. They are recall gaps.

Spaced repetition is how you close them. You practice computing circular distances, writing the shift counting loop, and explaining why d + 26 * j works, at increasing intervals. After a few rounds, the pattern is automatic. You see "circular shift" and "limited moves" in a problem, and the counting approach flows out naturally.

Related posts

• Valid Anagram - Character frequency counting as a foundation for string comparison
• Group Anagrams - Another problem using character-level analysis and hashing
• Longest Substring Without Repeating Characters - Sliding window string technique

CodeBricks breaks Can Convert String in K Moves into its circular shift computation and move assignment building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a string manipulation problem shows up in your interview, you do not think about it. You just write it.