#1540

Medium

LeetCode Problem Workspace

Can Convert String in K Moves

Determine if string s can be transformed into t within k moves using character shifts and hash table counting efficiently.

hash table string

Problem Statement

You are given two strings s and t of equal length and an integer k. In each move i (1 <= i <= k), you can shift any character in s forward in the alphabet, wrapping 'z' to 'a'. Each shift counts as one move, and multiple shifts can be applied over different moves.

Your goal is to determine whether it is possible to convert s into t within k moves. For example, shifting a character by i times moves it forward i positions in the alphabet, and repeated shifts of the same character must be accounted for in a hash table to ensure they fit within the move limit.

Examples

Example 1

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

Output: true

In the 6th move, we shift 'i' 6 times to get 'o'. And in the 7th move we shift 'n' to get 'u'.

Example 2

Input: s = "abc", t = "bcd", k = 10

Output: false

We need to shift each character in s one time to convert it into t. We can shift 'a' to 'b' during the 1st move. However, there is no way to shift the other characters in the remaining moves to obtain t from s.

Example 3

Input: s = "aab", t = "bbb", k = 27

Output: true

In the 1st move, we shift the first 'a' 1 time to get 'b'. In the 27th move, we shift the second 'a' 27 times to get 'b'.

Constraints

1 <= s.length, t.length <= 10^5
0 <= k <= 10^9
s, t contain only lowercase English letters.

Solution Approach

Compute Required Shifts

Iterate through s and t simultaneously and calculate the difference in positions for each character, considering wrap-around. Store the count of each required shift in a hash table to track how many characters need the same number of shifts.

Distribute Shifts Across Moves

For each unique shift value, check if the total number of moves needed for all characters with that shift fits within k. Leverage the fact that adding multiples of 26 to a shift produces the same result, allowing repeated shifts to be scheduled in later moves without exceeding k.

Validate Conversion Possibility

After computing all shift distributions, iterate through the hash table and confirm that each required shift can be completed within k moves. If any shift exceeds k when accounting for repeated occurrences, return false; otherwise, return true.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for iterating over s and t and updating the hash table, where n is the string length. Space complexity is O(26) = O(1) for the shift frequency hash table, independent of n.

What Interviewers Usually Probe

The problem tests the ability to use a hash table for counting frequencies of required character shifts.
Watch for off-by-one errors in calculating alphabet shifts with wrap-around from 'z' to 'a'.
Efficiently handling repeated shifts using multiples of 26 is key to staying within k moves.

Common Pitfalls or Variants

Common pitfalls

Failing to consider wrap-around shifts correctly, e.g., 'z' to 'a' as one move.
Not accounting for multiple characters needing the same shift, causing move count overflow.
Assuming shifts beyond k are valid without scheduling repeated shifts in multiples of 26.

Follow-up variants

Allow backward shifts and check if s can convert to t in k moves using positive and negative shifts.
Limit the alphabet to a subset and verify conversion feasibility within k moves for constrained letters.
Introduce variable move costs for different characters and determine if s can convert to t within total cost k.

FAQ

What is the main strategy to solve Can Convert String in K Moves efficiently?

Use a hash table to count required shifts for each character and schedule repeated shifts in multiples of 26 to stay within k moves.

Why is a hash table important in this problem?

It tracks how many characters need the same number of shifts, ensuring that the total moves do not exceed k when shifts repeat.

How do wrap-around shifts affect the solution?

Shifting 'z' to 'a' counts as one move and all shifts must be calculated modulo 26 to correctly schedule within k moves.

Can this solution handle very large k values?

Yes, because repeated shifts are distributed in multiples of 26, allowing any k up to 10^9 to be evaluated efficiently.

What is a common failure mode in this Hash Table plus String problem?

Ignoring repeated shifts or wrap-around effects can cause false negatives when determining if s can convert to t within k moves.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        cnt = [0] * 26
        for a, b in zip(s, t):
            x = (ord(b) - ord(a) + 26) % 26
            cnt[x] += 1
        for i in range(1, 26):
            if i + 26 * (cnt[i] - 1) > k:
                return False
        return True

Continue Practicing

#1542 find longest awesome substring #1525 number of good ways to split a string #1496 path crossing