LeetCode 1540 - Can Convert String in K Moves

Difficulty: 🟡 Medium
Topics: Hash Table, String

Solution

Problem Understanding

The problem is asking whether it is possible to convert one string s into another string t using at most k moves, following specific shifting rules. Each move allows you to choose a character in s that has not been moved before and shift it forward in the alphabet exactly i times, where i is the move number (starting from 1). The shifts wrap around from 'z' to 'a'. You can also choose to skip a move without shifting any character. The input consists of the strings s and t, and the integer k representing the maximum number of moves allowed. The output is a boolean indicating whether the conversion is possible.

The constraints tell us that s and t can each have up to 10^5 characters and k can be very large, up to 10^9. This means we cannot simulate every possible move sequentially; we need a solution that directly calculates feasibility. Important edge cases include when s and t are already equal, when the shifts required exceed k, or when multiple characters require the same shift, potentially exceeding the available move numbers.

Approaches

The brute-force approach would try every combination of choosing which character to shift at each move from 1 to k. This is correct but infeasible because there are k moves and n characters, making it exponentially large and impossible for the input constraints.

The optimal approach is based on the insight that the shift required for each character can be computed independently. For each position i, compute the difference between t[i] and s[i] in the alphabet modulo 26. If multiple characters require the same shift d, each occurrence after the first must be delayed by 26 moves (since shifts are modulo 26). This allows us to compute the maximum move number required for each shift and check if it is less than or equal to k. If all required shifts can be assigned to a move number ≤ k, the conversion is possible.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k^n)	O(n)	Trying all combinations of moves for each character
Optimal	O(n)	O(26)	Compute required shifts modulo 26 and check feasibility

Algorithm Walkthrough

Initialize an array shift_count of size 26 to zero. Each index i will store how many characters require a shift of i.
Iterate through each character index i from 0 to n-1. Compute the shift required to convert s[i] to t[i] as (ord(t[i]) - ord(s[i])) % 26.
Increment shift_count[shift] for the computed shift if the shift is not zero.
For each shift value d from 1 to 25, compute the maximum move number needed as d + 26 * (count - 1), where count is shift_count[d]. This accounts for characters that require the same shift being spaced by 26 moves.
If any required move number exceeds k, return False since conversion is impossible.
If all required shifts fit within k moves, return True.

This algorithm works because the modulo 26 arithmetic ensures that each shift can only occur in moves d, d+26, d+52,..., which corresponds to the repeated use of the same shift requirement. By tracking the maximum move number needed for each shift, we guarantee that no shift exceeds k moves.

Python Solution

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

The Python code first ensures s and t have the same length. It then computes the shift required for each character and counts how many times each shift occurs. For each non-zero shift, it calculates the maximum move number required. If this exceeds k, the function returns False; otherwise, it returns True.

Go Solution

func canConvertString(s string, t string, k int) bool {
    if len(s) != len(t) {
        return false
    }
    
    shiftCount := make([]int, 26)
    
    for i := 0; i < len(s); i++ {
        diff := (int(t[i]-s[i]) + 26) % 26
        if diff != 0 {
            shiftCount[diff]++
        }
    }
    
    for d := 1; d < 26; d++ {
        if shiftCount[d] > 0 {
            maxMove := d + 26*(shiftCount[d]-1)
            if maxMove > k {
                return false
            }
        }
    }
    
    return true
}

The Go implementation mirrors the Python solution. It handles modulo arithmetic carefully to avoid negative numbers, uses slices for shift counting, and iterates to check maximum moves. The logic is otherwise identical.

Worked Examples

Example 1: s = "input", t = "ouput", k = 9

i	s[i]	t[i]	diff	shift_count
0	i	o	6	shift_count[6] = 1
1	n	u	7	shift_count[7] = 1
2	p	p	0	-
3	u	u	0	-
4	t	t	0	-

Max move for shift 6 = 6 ≤ 9, max move for shift 7 = 7 ≤ 9, so return True.

Example 2: s = "abc", t = "bcd", k = 10

i	s[i]	t[i]	diff	shift_count
0	a	b	1	shift_count[1] = 1
1	b	c	1	shift_count[1] = 2
2	c	d	1	shift_count[1] = 3

Max move for shift 1 = 1 + 26*(3-1) = 53 > 10, so return False.

Example 3: s = "aab", t = "bbb", k = 27

i	s[i]	t[i]	diff	shift_count
0	a	b	1	shift_count[1] = 1
1	a	b	1	shift_count[1] = 2
2	b	b	0	-

Max move for shift 1 = 1 + 26*(2-1) = 27 ≤ 27, so return True.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass over the strings to compute differences and shift counts
Space	O(1)	Fixed array of size 26 for shift counts, independent of input size

The time complexity is linear in the string length. Space complexity is constant because the shift counts array has a fixed size of 26.

Test Cases

# Basic examples
assert Solution().canConvertString("input", "ouput", 9) == True  # Example 1
assert Solution().canConvertString("abc", "bcd", 10) == False  # Example 2
assert Solution().canConvertString("aab", "bbb", 27) == True   # Example 3

# Edge cases
assert Solution().canConvertString("a", "a", 0) == True         # No moves needed
assert Solution().canConvertString("a", "b", 1) == True         # Single shift possible
assert Solution().canConvertString("a", "b", 0) == False        # Shift needed but no moves
assert Solution().canConvertString("aaa", "bbb", 26) == False   # Insufficient moves for multiple same shifts
assert Solution().canConvertString("aaa", "bbb", 27) == True    # Enough moves for multiple same shifts
assert Solution().canConvertString("xyz", "abc", 54) == True    # Wrap around shifts

Test	Why
Basic examples	Validates correctness on problem examples
Single character	Checks minimal input and 0 moves edge case
Multiple same shifts	Ensures modulo 26 logic handles repeated shifts correctly
Wrap-around