1540. Can Convert String in K Moves - Leetcode Solution

Code Implementation

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        from collections import Counter
        shifts = [0] * 26
        for a, b in zip(s, t):
            diff = (ord(b) - ord(a)) % 26
            if diff != 0:
                shifts[diff] += 1
        for i in range(1, 26):
            # i + 26 * (shifts[i] - 1) must be <= k
            if i + 26 * (shifts[i] - 1) > k:
                return False
        return True

class Solution {
public:
    bool canConvertString(string s, string t, int k) {
        if (s.length() != t.length()) return false;
        vector<int> shifts(26, 0);
        for (int i = 0; i < s.length(); ++i) {
            int diff = (t[i] - s[i] + 26) % 26;
            if (diff != 0) {
                shifts[diff]++;
            }
        }
        for (int i = 1; i < 26; ++i) {
            if (i + 26 * (shifts[i] - 1) > k) {
                return false;
            }
        }
        return true;
    }
};

class Solution {
    public boolean canConvertString(String s, String t, int k) {
        if (s.length() != t.length()) return false;
        int[] shifts = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            int diff = (t.charAt(i) - s.charAt(i) + 26) % 26;
            if (diff != 0) {
                shifts[diff]++;
            }
        }
        for (int i = 1; i < 26; ++i) {
            if (i + 26 * (shifts[i] - 1) > k) {
                return false;
            }
        }
        return true;
    }
}

var canConvertString = function(s, t, k) {
    if (s.length !== t.length) return false;
    let shifts = new Array(26).fill(0);
    for (let i = 0; i < s.length; ++i) {
        let diff = (t.charCodeAt(i) - s.charCodeAt(i) + 26) % 26;
        if (diff !== 0) {
            shifts[diff]++;
        }
    }
    for (let i = 1; i < 26; ++i) {
        if (i + 26 * (shifts[i] - 1) > k) {
            return false;
        }
    }
    return true;
};

Problem Description

Given two strings s and t of equal length, and an integer k, determine if you can convert s into t in at most k moves. In each move, you can choose any character in s and shift it forward by 1 (from 'a' to 'b', ..., 'z' to 'a'). Each move can only shift one character by one position, and you can apply at most k moves in total. Each move can be applied to any character, and the same character can be shifted multiple times. You must achieve the exact target string t after all moves.

Thought Process

At first glance, you might think of brute-forcing all possible ways to shift characters, but that would be extremely inefficient. Instead, notice that each character in s needs to be shifted a certain number of times to match the corresponding character in t. The key insight is to count, for each possible shift (from 1 to 25), how many characters need that shift. Since you can only use each move (i.e., each shift amount) once per 26 moves (because after 26 moves, the same character can be shifted again), you need to ensure that for each shift amount, the total number of required moves doesn't exceed what's possible within k moves.

Solution Approach

Step 1: If the lengths of s and t are not equal, immediately return false.
Step 2: For each character position, compute the shift needed to convert s[i] to t[i]. The shift is (ord(t[i]) - ord(s[i])) % 26.
Step 3: Count how many times each shift (from 1 to 25) is needed.
Step 4: For each shift amount i (from 1 to 25):

Suppose you need shifts[i] times of shift i. The first can be done at move i, the next at i + 26, the next at i + 52, etc.
The last such move will be at i + 26 * (shifts[i] - 1). If this exceeds k, it's impossible.

Step 5: If all shift requirements can be satisfied within k moves, return true. Otherwise, return false.

This approach uses an array (or map) to count shift requirements and checks if they fit within the allowed moves, making it efficient and easy to implement.

Example Walkthrough

Suppose s = "input", t = "jovpu", k = 20.
Let's compare each character:

s[0]='i' to t[0]='j': needs 1 shift
s[1]='n' to t[1]='o': needs 1 shift
s[2]='p' to t[2]='v': needs 6 shifts
s[3]='u' to t[3]='p': needs 21 shifts
s[4]='t' to t[4]='u': needs 1 shift

Now, count the shifts:

Shift 1: needed 3 times
Shift 6: needed 1 time
Shift 21: needed 1 time

For shift 1, the moves needed are at 1, 27, and 53. The last is 53, which is greater than k=20, so it's impossible. The function returns false.

Time and Space Complexity

Brute-force approach: Would attempt all possible move combinations, leading to exponential time and space complexity, which is not practical.
Optimized approach:
- Time Complexity: O(n), where n is the length of the strings, since we only iterate once through the strings and then once through the 25 possible shifts.
- Space Complexity: O(1), as the shift count array is always of size 26, regardless of input size.

Summary

The key insight is to count, for each needed shift, how many such moves are required and check if they fit within the total allowed moves k. By leveraging modular arithmetic and a fixed-size counter, we avoid brute-force and achieve an efficient solution. The method is elegant because it reduces the problem to simple counting and arithmetic, making it both fast and easy to understand.

AlgoMap.io

Want Help Cracking FAANG?