Is Can Convert String in K Moves easy or hard?

The problem is rated Medium on LeetCode. The implementation is straightforward once the cyclic shift pattern is recognized, but identifying the 26-move repetition constraint is the key insight that makes the problem challenging.

Can Convert String in K Moves Python/Java solution

The Python or Java solution iterates through both strings, calculates the cyclic shift difference, and counts occurrences using an array of size 26. Each occurrence schedules its required move using the formula d + 26*(count-1) and verifies it does not exceed k.

How to solve Can Convert String in K Moves in O(n)?

Iterate through both strings and compute the cyclic shift difference for each index using (t[i] - s[i] + 26) % 26. Track how many times each shift value appears. For the j-th occurrence of shift d, the required move becomes d + 26*(j-1). If that value exceeds k, the conversion cannot be completed.

What is the best approach for Can Convert String in K Moves?

The optimal approach computes the required shift for each character and tracks how many times that shift occurs. Because identical shifts can only be reused every 26 moves, the j-th occurrence must happen at move d + 26*(j-1). Checking this constraint for every character gives an O(n) time and O(1) space solution.

Is Can Convert String in K Moves asked at Google/Amazon/Meta?

Problems involving cyclic shifts and frequency tracking appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the underlying concepts of modular arithmetic, string manipulation, and counting conflicts are common interview patterns.

What data structure is used in Can Convert String in K Moves?

A fixed-size frequency array (or hash map keyed by shift value) is used to track how many times each shift from 1–25 occurs. Because the alphabet has only 26 letters, an integer array of length 26 is sufficient and keeps space complexity constant.

What is the time complexity of Can Convert String in K Moves?

The algorithm runs in O(n) time where n is the string length. Each character pair is processed once to compute the cyclic shift and update a constant-size tracking structure. Space complexity is O(1) because only an array of size 26 is required.

Description Hints 2 Solution Video 12:15

1540. Can Convert String in K Moves

Medium38.2% acceptance1 company

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

During the i^th (1 <= i <= k) move 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.

Example 1:

Input: s = "input", t = "ouput", k = 9
Output: true
Explanation: 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
Explanation: 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
Explanation: 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: