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:
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.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^50 <= k <= 10^9s, t contain only lowercase English letters.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.
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.
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).
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.
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.
| Approach | Complexity |
|---|---|
| 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 | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Basic Shift Calculation with Frequency Check | O(n) | O(1) | Clear and easy approach when explaining the shift conflict logic during interviews |
| Optimized Shift Tracking | O(n) | O(1) | Preferred when implementing a cleaner single-pass scheduling solution |
Can Convert String in K Moves | Leetcode 1540 • Competitive Coding • 674 views views
Watch 9 more video solutions →Practice Can Convert String in K Moves with our built-in code editor and test cases.
Practice on FleetCode