Can Convert String In K Moves - Leetcode Solution

Problem Statement: Given two strings s and t, your goal is to convert s into t in k moves or less.

During each move you can choose a single character in s and replace it with any other character.

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 = "output", k = 9 Output: True Explanation: In 6 moves we can convert "input" to "uuput". Then, we can use 1 more move to replace "u" with "o". Example 2:

Input: s = "abc", t = "def", k = 3 Output: False Explanation: The characters "a", "b", and "c" cannot be replaced at all. Example 3:

Input: s = "aaa", t = "aaaa", k = 5 Output: True Explanation: In 5 moves we can add one 'a' to s and transform it into "aaaa".

Solution: We find out three cases here:

1. If k is greater than or equal to the sum of the lengths of given two strings, then we can always convert s to t. Because with k moves, we can replace each character of s with one of the character of t. So, in this case, the answer will be True.

2. If k is less than the difference between the lengths of given two strings, then it is impossible to convert s into t in k moves. Because we need more moves to make s and t of equal length by adding or removing characters. So, in this case, the answer will be False.

3. If k is neither greater than or equal to the sum of the lengths nor less than the difference between the lengths of given two strings, then we have to check if s can be converted to t in k moves or less. We can do this by counting the number of common characters between s and t till the position where they differ. Then, if k is greater than or equal to the number of operations required to replace the characters to make s equal to t, then we can convert s to t in k moves or less. Otherwise, we can't.

Let's see the implementation of the above solution:

class Solution: def canConvertString(self, s: str, t: str, k: int) -> bool:

    # if sum of lengths of s and t is less than k, we can convert s to t
    if len(s) + len(t) <= k:
        return True
    
    # if k is less than the difference between lengths of s and t, we can't convert s to t
    if len(t) < len(s) or len(t) - len(s) > k:
        return False
    
    # count the number of operations required to make s equal to t
    operations = 0
    freq = [0] * 26
    for i in range(len(s)):
        diff = (ord(t[i]) - ord(s[i]) + 26) % 26
        if diff != 0:
            freq[diff] += 1
            operations = max(operations, (diff - 1) * ((k - diff) // 26) + freq[diff])
            
    return k >= operations

1