Can Convert String in K Moves — Medium Problem & Solution

Problem statement

You have k moves, numbered 1 through k. On move i you may pick an index of s not chosen before and shift its character forward by i positions in the alphabet, wrapping z around to a. You may also skip a move.

Return true if s can be turned into t within those k moves.

Example 1

Input: s = "input", t = "ouput", k = 9
Output: true
Explanation: Shift index 0 by 6 on move 6 and index 4 by 1 on move 1.

Example 2

Input: s = "abc", t = "bcd", k = 10
Output: false
Explanation: All three need a shift of 1, but only moves 1 and 27 provide that — and 27 is beyond k.

Example 3

Input: s = "aab", t = "bbb", k = 27
Output: true
Explanation: The two shifts of 1 use moves 1 and 27.

Constraints

• 1 <= s.length, t.length <= 100000
• 0 <= k <= 1000000
• s and t consist of lowercase English letters.

How to solve Can Convert String in K Moves

The required shift per index is forced, and the move numbers that produce a given shift form an arithmetic progression with step 26. Counting how many indices already claimed each shift tells you exactly which move number the next one needs.

Approach

1. If the two strings have different lengths, the answer is immediately false.
2. For each index, compute shift = (t[i] - s[i] + 26) % 26 and skip it when it is 0.
3. Look up how many indices have already taken this shift, say used; the move needed is shift + 26 * used.
4. If that move exceeds k, return false; otherwise record the claim and continue.

Why it works

Move m shifts by m mod 26, so the moves capable of shift d are exactly d, d+26, d+52, …. Assigning them in increasing order is optimal — any other assignment uses a move at least as large for some index. The check therefore fails only when no assignment exists.

Complexity

• Time — O(n)
• Space — O(26)

Pitfalls

• Counting a shift of 0 as needing a move wastes the budget and rejects valid inputs.
• Forgetting the length check compares mismatched indices.
• shift + 26 * used overflows 32 bits only for absurd inputs, but a long is the safe habit.

Reference solution

Python

def canConvertString(s: str, t: str, k: int) -> bool:
    if len(s) != len(t):
        return False
    used = [0] * 26
    for a, b in zip(s, t):
        shift = (ord(b) - ord(a)) % 26
        if shift == 0:
            continue
        move = shift + 26 * used[shift]
        used[shift] += 1
        if move > k:
            return False
    return True

JavaScript

var canConvertString = function(s, t, k) {
    if (s.length !== t.length) return false;
    var used = [];
    for (var u = 0; u < 26; u++) used.push(0);
    for (var i = 0; i < s.length; i++) {
        var shift = ((t.charCodeAt(i) - s.charCodeAt(i)) % 26 + 26) % 26;
        if (shift === 0) continue;
        var move = shift + 26 * used[shift];
        used[shift]++;
        if (move > k) return false;
    }
    return true;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Make Three Strings Equal Medium
• Number of Ways to Divide a Long Corridor Medium
• Maximum Number of Non-overlapping Palindrome Substrings Medium
• Count Number of Texts Medium
• Delete Characters to Make Fancy String Medium
• Count Number of Homogenous Substrings Medium