Problem

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.

Examples

Example 1

1
2
3

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

1
2
3

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

1
2
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

Method 1 – Greedy Counting of Required Shifts

Intuition

For each character, calculate how many shifts are needed to convert s[i] to t[i] (modulo 26). For each possible shift, count how many times it is needed. Since each shift of value x can only be performed once every 26 moves (i.e., at moves x, x+26, x+52, …), check if the required number of shifts for each value fits within k moves.

Approach

  1. If s and t are not the same length, return false.
  2. For each index, compute the shift needed: (ord(t[i]) - ord(s[i])) % 26.
  3. For each shift value from 1 to 25, count how many times it is needed.
  4. For each shift value x, the last time it can be performed is x + 26 * (count[x] - 1). If this exceeds k, return false.
  5. If all shifts fit within k, return true.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public boolean canConvertString(String s, String t, int k) {
        if (s.length() != t.length()) return false;
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); i++) {
            int diff = (t.charAt(i) - s.charAt(i) + 26) % 26;
            if (diff != 0) cnt[diff]++;
        }
        for (int x = 1; x < 26; x++) {
            if (x + 26 * (cnt[x] - 1) > k) return false;
        }
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        cnt = [0] * 26
        for a, b in zip(s, t):
            diff = (ord(b) - ord(a)) % 26
            if diff != 0:
                cnt[diff] += 1
        for x in range(1, 26):
            if x + 26 * (cnt[x] - 1) > k:
                return False
        return True

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)