Skip to main content
Talentd

Can Convert String in K Moves - Solution & Explanation

MediumHash TableString8 min readAsked at: Infosys
Practice this problem

Problem Statement

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

During the ith (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:

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

Approach Overview

Problem Overview: You are given two strings s and t of equal length and an integer k. In move i (1 ≤ i ≤ k), you may pick an unused index and shift its character forward by i positions in the alphabet (cyclic). The goal is to determine whether s can be transformed into t within k moves.

Approach 1: Basic Shift Calculation with Frequency Check (O(n) time, O(1) space)

Iterate through both strings and compute the shift required for each position. The shift is (t[i] - s[i] + 26) % 26. A shift of 0 means the characters already match and requires no move. For non‑zero shifts, track how many times that shift value appears using a small frequency array of size 26.

The key constraint: the same shift value cannot be used in the same move twice. If a shift value d appears multiple times, subsequent occurrences must wait for the next cycle of that shift, which occurs every 26 moves. That means the j-th occurrence requires move d + 26*(j-1). If this required move exceeds k, the conversion is impossible.

This method works because the alphabet size is fixed (26), so the frequency array remains constant space. The algorithm scans the strings once and performs constant-time checks per character. It relies on basic arithmetic and counting, making it a clean application of string manipulation and hash table style frequency tracking.

Approach 2: Optimized Shift Tracking (O(n) time, O(1) space)

Instead of counting frequencies first and validating later, track the next available move for each shift dynamically. Maintain an array nextMove[26] where each index stores the earliest move number available for that shift value.

For each character pair, compute the required shift d. If d == 0, continue. Otherwise check the next valid move: if the shift hasn't been used before, the move is simply d. If it was used previously, schedule the next occurrence at nextMove[d] + 26. Update the array and verify the scheduled move does not exceed k.

This approach processes constraints immediately as you iterate. It avoids a separate validation pass and keeps the logic centered on scheduling moves. The complexity remains linear with constant extra memory since the alphabet size is fixed.

Recommended for interviews: Start by explaining the shift calculation and why identical shifts conflict with each other. The frequency-based method demonstrates clear reasoning and works well on a whiteboard. The optimized scheduling approach shows deeper insight into how the move sequence repeats every 26 operations, which is typically the level interviewers expect for medium-level string problems.

Approach 1: Basic Shift Calculation with Frequency Check

This approach involves calculating the shift needed for each character in s to become the corresponding character in t. For each position, compute the required shift and check if this shift can be performed by one of the next k moves. Use an array to track the number of times a shift of a specific magnitude has been requested in order to ensure uniqueness of moves for each character.

This Python solution first checks if strings s and t have the same length. If not, returns False. It iterates over each pair of corresponding characters in s and t, calculates the shift needed, and keeps a count of each shift. If a calculated move is needed more than once, it considers the move's repeat, accounting for 26 character wraps. Finally, it verifies if these moves fall within the number k of allowed operations.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n), where n is the length of the string, since we iterate once over the characters to calculate shifts. Space Complexity: O(1), as the array size of max_shifts_needed remains constant (26).

Try this approach in the editor →

Approach 2: Optimized Shift Tracking

This method optimizes tracking of the number of shifts needed by using modular arithmetic directly to determine and validate shifts on-the-fly, without counting beforehand. This approach suits cases involving large k and more complex distributions of required shifts.

This C++ solution calculates the necessary shift for each character pairing in s and t directly as they are iterated. It adjusts for character wrapping via modulus arithmetic and determines the number of times any particular shift must occur. Finally, it validates that these shifts can occur within the confines of k moves.

Code

C++C#

C++

C#

Complexity

Time Complexity: O(n) due to a single pass iteration over the strings. Space Complexity: O(1) with a of size 26 used for shifts.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Basic Shift Calculation with Frequency Check

Time Complexity: O(n), where n is the length of the string, since we iterate once over the characters to calculate shifts. Space Complexity: O(1), as the array size of max_shifts_needed remains constant (26).

Optimized Shift Tracking

Time Complexity: O(n) due to a single pass iteration over the strings. Space Complexity: O(1) with a of size 26 used for shifts.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Basic Shift Calculation with Frequency CheckO(n)O(1)Clear and easy approach when explaining the shift conflict logic during interviews
Optimized Shift TrackingO(n)O(1)Preferred when implementing a cleaner single-pass scheduling solution

Video Solution

Can Convert String in K Moves | Leetcode 1540 • Competitive Coding • 679 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Can Convert String in K Moves with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Cost to Convert String I

Next

Minimum Cost to Convert String II