{x}
blog image

Can Convert String in K Moves

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.

Solution Explanation

This problem asks whether we can convert string s to string t using at most k moves. In each move, we can choose an index in s and shift the character at that index by the move number. The core idea is to determine the necessary shifts for each character and check if those shifts can be accommodated within the k move limit.

Algorithm:

  1. Length Check: First, verify that the lengths of s and t are equal. If not, conversion is impossible, and we return false.

  2. Shift Calculation: Iterate through the strings simultaneously. For each pair of characters s[i] and t[i], calculate the required shift x. We use the modulo operator (% 26) to handle wraparound (e.g., shifting 'z' becomes 'a'). The formula (ord(b) - ord(a) + 26) % 26 efficiently computes this. ord() gets the ASCII value of the character.

  3. Shift Count: Store the counts of each required shift in a frequency array cnt (of size 26). cnt[x] will hold the number of times a shift of x is needed.

  4. Move Feasibility Check: Iterate through the shift counts from 1 to 25 (shift 0 means no shift is needed). For each shift i, calculate the total moves required to perform all shifts of size i. This is i + 26 * (cnt[i] - 1). The intuition is that if we have multiple shifts of size i, we can't perform them all concurrently (each shift is tied to a unique move). If this total exceeds k, the conversion is impossible, and we return false.

  5. Return True: If all shifts are feasible within k moves, the function returns true.

Time Complexity Analysis:

  • The string iteration takes O(n) time, where n is the length of the strings.
  • The shift count array creation and iteration take O(1) time (26 is a constant).
  • Therefore, the overall time complexity is O(n), dominated by the string traversal.

Space Complexity Analysis:

  • The space used is dominated by the cnt array, which has a constant size of 26.
  • Therefore, the space complexity is O(1). It's constant regardless of input string size.

Code Explanations (Python, Java, C++, Go):

The provided code implements the algorithm efficiently. All versions follow the same core logic:

  1. Length Check: if len(s) != len(t): return False; (Python, similar checks in other languages)
  2. Shift Calculation & Count: The loop calculates x and increments cnt[x].
  3. Feasibility Check: The loop iterates through cnt, calculating the required moves for each shift size and comparing to k.
  4. Return Value: Returns true if all checks pass; otherwise, false.

The different languages only vary in syntax and data structure specifics (e.g., array declaration and access). The underlying algorithm remains consistent across all implementations.