Can Convert String in K Moves - Practice Coding Problems

Can Convert String in K Moves - Problem

Given two strings s and t, your goal is to convert s into t in k moves or less.

During the i-th move (1 <= i <= k) you can:

Choose any index j (1-indexed) from s, such that 1 <= j <= s.length and j has not been chosen in any previous move, and shift the character at that index i times.
Do nothing.

Shifting a character means replacing it by the next letter in the alphabet (wrapping around so that 'z' becomes 'a'). Shifting a character by i means applying the shift operations i times.

Remember that any index j can be picked at most once.

Return true if it's possible to convert s into t in no more than k moves, otherwise return false.

Input & Output

Example 1 — Basic Conversion

$ Input: s = "input", t = "ouput", k = 9

› Output: true

💡 Note: We need to convert 'i'→'o' (shift 6), 'n'→'u' (shift 7), 'p'→'p' (shift 0, no change), 'u'→'u' (shift 0, no change), 't'→'t' (shift 0, no change). We need shifts of 6 and 7, which can be achieved with moves 6 and 7 respectively, both ≤ 9.

Example 2 — Impossible Case

$ Input: s = "abc", t = "bcd", k = 2

› Output: false

💡 Note: We need 'a'→'b' (shift 1), 'b'→'c' (shift 1), 'c'→'d' (shift 1). All three positions need shift amount 1, but we only have moves 1 and 2. Move 1 creates shift 1, move 2 creates shift 2. We need 3 positions with shift 1 but only have 1 move that creates shift 1.

Example 3 — Wrap Around

$ Input: s = "ruu", t = "rvv", k = 3

› Output: true

💡 Note: We need 'r'→'r' (no change), 'u'→'v' (shift 1), 'u'→'v' (shift 1). Two positions need shift 1. We have moves 1, 2, 3. Move 1 creates shift 1. We need 2 shifts of amount 1, but only move 1 can create shift 1, so this should be false. Wait, let me recalculate: we need only 2 positions with shift 1, and we have move 1 available, but that's only 1 move. Actually this should be false.

Constraints

1 ≤ s.length, t.length ≤ 10⁵
0 ≤ k ≤ 10⁹
s and t consist of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Identify positions where s[i] ≠ t[i] and calculate required shifts

Move Assignment

Determine if available moves 1,2,...,k can satisfy all shift requirements

Result

Return true if conversion possible, false otherwise

Key Takeaway

🎯 Key Insight: Each move i can only be used once and creates shift i%26, so we must count shift requirements and verify sufficient moves exist

Asked in

G Google 15 a Amazon 12

The key insight is that we can only use each move number once, and move i creates a shift of i % 26. We need to count how many positions require each shift amount, then check if we have enough moves to satisfy all requirements. The optimal greedy approach assigns moves efficiently in O(n) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Assignment	O(n)	O(1)	Optimally assign the smallest possible move numbers to each required shift
Count Required Shifts	O(n + k)	O(26)	Count how many positions need each shift amount, then check if we have enough moves
Try All Combinations	O(k!)	O(n)	Generate all possible ways to assign moves to positions and check if any works

Greedy Assignment — Algorithm Steps

Group positions by shift amount needed
For each shift amount, find all move numbers that can create it
Assign moves greedily starting from smallest

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Shifts

Count how many positions need each shift amount (1-26)

Assign Greedily

For each shift, use the smallest available moves that can create it

Verify

Check if all requirements can be satisfied within k moves

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(char* s, char* t, int k) {
    int len = strlen(s);
    if (len != strlen(t)) return false;
    
    int shiftCount[27] = {0};
    
    for (int i = 0; i < len; i++) {
        if (s[i] != t[i]) {
            int shift = (t[i] - s[i] + 26) % 26;
            if (shift == 0) shift = 26;
            shiftCount[shift]++;
        }
    }
    
    int move = 1;
    for (int shift = 1; shift <= 26; shift++) {
        int countNeeded = shiftCount[shift];
        
        while (countNeeded > 0 && move <= k) {
            if (move % 26 == shift % 26) {
                countNeeded--;
            }
            move++;
        }
        
        if (countNeeded > 0) return false;
    }
    
    return true;
}

int main() {
    char s[1001], t[1001];
    int k;
    
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    fgets(t, sizeof(t), stdin);
    t[strcspn(t, "\n")] = 0;
    scanf("%d", &k);
    
    bool result = solution(s, t, k);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to count shifts, constant time to check move availability

✓ Linear Growth

Space Complexity

O(1)

Only uses fixed-size arrays for counting (max 26 shift amounts)

✓ Linear Space

23.5K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Assignment — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler