Can Convert String in K Moves

Medium
649.

Can Convert String in K Moves

Can Convert String in K Moves is a medium coding problem on strings, hash table and greedy, asked in Amazon, Google and Adobe interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {string} t
 * @param {number} k
 * @return {boolean}
 */
var canConvertString = function(s, t, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Can Convert String in K Moves — Problem & Solution

Can Convert String in K Moves solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Can Convert String in K Moves is a medium coding problem on strings, hash table and greedy, asked in Amazon, Google and Adobe interviews.

  • Difficulty: Medium
  • Topics: Strings, Hash Table, Greedy
  • Asked at: Amazon, Google, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

Hints for Can Convert String in K Moves

  1. Hint 1

    Each index needs one fixed shift: (t[i] - s[i] + 26) % 26. A shift of 0 costs no move at all.

  2. Hint 2

    Only moves d, d + 26, d + 52, … can deliver a shift of d, so several indices needing the same shift must queue up.

  3. Hint 3

    The j-th index (1-based) needing shift d must use move d + 26·(j-1).

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

Java

public static boolean canConvertString(String s, String t, int k) {
    if (s.length() != t.length()) return false;
    int[] used = new int[26];
    for (int i = 0; i < s.length(); i++) {
        int shift = ((t.charAt(i) - s.charAt(i)) % 26 + 26) % 26;
        if (shift == 0) continue;
        long move = (long) shift + 26L * used[shift];
        used[shift]++;
        if (move > k) return false;
    }
    return true;
}

C++

bool canConvertString(string s, string t, int k) {
    if (s.size() != t.size()) return false;
    vector<long long> used(26, 0);
    for (size_t i = 0; i < s.size(); i++) {
        int shift = ((t[i] - s[i]) % 26 + 26) % 26;
        if (shift == 0) continue;
        long long move = shift + 26LL * used[shift];
        used[shift]++;
        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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets