1540. Can Convert String in K Moves LeetCode Solution

Last updated: February 24, 2025

In this guide, you will get 1540. Can Convert String in K Moves LeetCode Solution with the best time and space complexity. The solution to Can Convert String in K Moves problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Can Convert String in K Moves solution in C++
Can Convert String in K Moves solution in Java
Can Convert String in K Moves solution in Python
Additional Resources

1540. Can Convert String in K Moves LeetCode Solution image

Problem Statement of 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.

Complexity Analysis

Time Complexity: O(|\texttt{s}|)
Space Complexity: O(26) = O(1)

1540. Can Convert String in K Moves LeetCode Solution in C++

class Solution {
 public:
  bool canConvertString(string s, string t, int k) {
    if (s.length() != t.length())
      return false;

    // e.g. s = "aab", t = "bbc", so shiftCount[1] = 3
    // 1. a -> b, need 1 move.
    // 2. a -> b, need 1 + 26 moves.
    // 3. b -> c, need 1 + 26 * 2 moves.
    vector<int> shiftCount(26);

    for (int i = 0; i < s.length(); ++i)
      ++shiftCount[(t[i] - s[i] + 26) % 26];

    for (int shift = 1; shift < 26; ++shift)
      if (shift + 26 * (shiftCount[shift] - 1) > k)
        return false;

    return true;
  }
};
/* code provided by PROGIEZ */

1540. Can Convert String in K Moves LeetCode Solution in Java

class Solution {
  public boolean canConvertString(String s, String t, int k) {
    if (s.length() != t.length())
      return false;

    // e.g. s = "aab", t = "bbc", so shiftCount[1] = 3
    // 1. a -> b, need 1 move.
    // 2. a -> b, need 1 + 26 moves.
    // 3. b -> c, need 1 + 26 * 2 moves.
    int[] shiftCount = new int[26];

    for (int i = 0; i < s.length(); ++i)
      ++shiftCount[(t.charAt(i) - s.charAt(i) + 26) % 26];

    for (int shift = 1; shift < 26; ++shift)
      if (shift + 26 * (shiftCount[shift] - 1) > k)
        return false;

    return true;
  }
}
// code provided by PROGIEZ

1540. Can Convert String in K Moves LeetCode Solution in Python

class Solution:
  def canConvertString(self, s: str, t: str, k: int) -> bool:
    if len(s) != len(t):
      return False

    # e.g. s = "aab", t = "bbc", so shiftCount[1] = 3
    # 1. a -> b, need 1 move.
    # 2. a -> b, need 1 + 26 moves.
    # 3. b -> c, need 1 + 26 * 2 moves.
    shiftCount = [0] * 26

    for a, b in zip(s, t):
      shiftCount[(ord(b) - ord(a) + 26) % 26] += 1

    for shift in range(1, 26):
      if shift + 26 * (shiftCount[shift] - 1) > k:
        return False

    return True
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents