1540. Can Convert String in K Moves

MediumHash TableString
Leetcode Link

Problem Description

In this problem, you are given two strings s and t, and an integer k. The goal is to determine if you can transform string s into string t by performing up to k moves. A move consists of picking an index j in string s and shifting the character at that index a certain number of times. Each character in s may only be shifted once, and the shift operation wraps around the alphabet (e.g., shifting 'z' by 1 results in 'a').

The key constraints are:

  • You can make no more than k moves in total.
  • Each move involves shifting one character of s by i positions in the alphabet, where 1 <= i <= k.
  • The index chosen for shifting in each move should not have been used in a previous move.
  • You can only shift a character to the next one in the alphabet, with 'z' changing to 'a'.

The task is to return true if s can be transformed into t using at most k moves under these rules; otherwise, return false.

Intuition

The solution approach starts by realizing that in order to change s into t, for each position where s and t differ, we need to calculate the number of shifts required to convert the character in s to the corresponding character in t. This can be done by finding the difference in their ASCII values and taking the modulus with 26 to handle the wrapping around the alphabet.

The next step is to keep track of the number of times each shift amount is needed. We use a list, cnt, to record the frequency of each required shift amount from 0 to 25 (since there are 26 letters in the alphabet). A shift amount of 0 means the characters are already the same, and no move is needed.

Once we have this frequency array, we check if any of these shifts can be performed within the move limit k. For each non-zero shift amount, we calculate when the last shift can occur. Since each shift amount can be used every 26 moves, we determine the maximum moves needed for each shift (i + 26 * (cnt[i] - 1)). If this exceeds k, it's impossible to transform s into t, and we return false.

The reason for subtracting 1 from cnt[i] is that the first occurrence of each shift amount does not have to wait for a full cycle—it can happen immediately. Hence, only subsequent occurrences (if any) need to be delayed by 26 moves each.

If none of the shifts exceeds the move limit k, then it is possible to transform s into t, and we return true.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the relationship between a tree and a graph?

Solution Approach

The implementation of the solution involves a few key steps that use simple data structures and algorithms.

  1. Length Check: First, we check if s and t are of equal length. If not, return False immediately because the problem states that only characters in s can be shifted, implying both strings must be of the same length to be convertible.

  2. Frequency Array: We create an array, cnt, of length 26 initialized to zero, which will hold the frequency of each shift amount required.

  3. Calculate Shifts: We loop over the characters of s and t simultaneously using Python's zip function. For each corresponding pair of characters (a, b), we calculate the shift required to turn a into b. The shift is calculated using the formula (ord(b) - ord(a) + 26) % 26, where ord() is a Python function that returns the ASCII value of a character. The addition of 26 before the modulus operation is to ensure a positive result for cases where b comes before a in the alphabet.

  4. Count the Shifts: We increment the count of the appropriate shift amount in the cnt array. If no shift is needed, the increment occurs at cnt[0].

  5. Move Validation: After calculating all the necessary shifts, we iterate over the cnt array (starting from index 1 since index 0 represents no shift). For each shift amount i, we find out how late this shift can occur by multiplying the number of full cycles (cnt[i] - 1) by the cycle length 26, and adding the shift amount i itself. The result tells us at which move number the last shift could feasibly happen. If this move number is greater than k, the transformation is not possible within the move limit, so we return False.

  6. Result: If none of the calculated shift timings exceed k, then it is verified that all characters from s can be shifted to match t within the move limit. Thus, the function returns True.

By using a frequency array and calculating the maximum move number needed for each shift, the algorithm efficiently determines the possibility of transformation without actually performing the moves, resulting in a less complex and time-efficient solution.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Example Walkthrough

Let's consider a simple example:

  • s = "abc"
  • t = "bcd"
  • k = 2

Step 1: Length Check

  • Both strings s and t are of equal length, which is 3. We can proceed with the transformation process.

Step 2: Frequency Array

  • We create an array cnt with length 26, initialized to zero: cnt = [0] * 26.

Step 3: Calculate Shifts

  • We loop over s and t in parallel and calculate the shift required:
    • For s[0]: 'a' to t[0]: 'b' requires 1 shift.
    • For s[1]: 'b' to t[1]: 'c' requires 1 shift.
    • For s[2]: 'c' to t[2]: 'd' requires 1 shift.
  • The shift calculations:
    • Shift for 'a' to 'b' is (ord('b') - ord('a') + 26) % 26 = 1.
    • Shift for 'b' to 'c' is (ord('c') - ord('b') + 26) % 26 = 1.
    • Shift for 'c' to 'd' is (ord('d') - ord('c') + 26) % 26 = 1.

Step 4: Count the Shifts

  • For each shift calculated, increment the corresponding index in cnt:
    • For shift 1: cnt[1] becomes 3 because we need to shift by 1 three times.

Step 5: Move Validation

  • We iterate through cnt starting from index 1:
    • For shift amount i = 1 and frequency cnt[1] = 3, calculate maximum move needed: i + 26 * (cnt[1] - 1) = 1 + 26 * (3 - 1) = 53 which exceeds k = 2, implying that it's impossible to conduct all required shifts within k moves.

As we can see, for the sample s and t, it would not be possible to transform s into t with only k moves since the latest move needed exceeds k. Thus, the false outcome would be the correct answer for this example.

Solution Implementation

1class Solution:
2    def can_convert_string(self, s: str, t: str, k: int) -> bool:
3        # If the lengths of the input strings differ, conversion is not possible
4        if len(s) != len(t):
5            return False
6      
7        # Initialize an array to keep count of the number of shifts for each character
8        shift_counts = [0] * 26
9      
10        # Iterate over the characters of both strings
11        for char_s, char_t in zip(s, t):
12            # Calculate the shift difference and take modulo 26 to wrap around the alphabet
13            shift = (ord(char_t) - ord(char_s) + 26) % 26
14            # Increment the count of the corresponding shift
15            shift_counts[shift] += 1
16      
17        # Check if the shifts can be achieved within the allowed operations 'k'
18        for i in range(1, 26):
19            # Calculate the maximum number of operations needed for this shift
20            # For multiple shifts 'i', we need to wait 26 more for each additional use
21            max_operations = i + 26 * (shift_counts[i] - 1)
22          
23            # If max_operations exceeds 'k', then it's not possible to convert the string
24            if max_operations > k:
25                return False
26      
27        # If all shifts are possible within the operations limit, return True
28        return True
29
30# Example usage:
31# solution_instance = Solution()
32# result = solution_instance.can_convert_string("input1", "input2", 10)
33# print(result) # Output: True or False depending on whether the conversion is possible
34
1class Solution {
2
3    // Method to determine if it's possible to convert string s to string t
4    // by shifting each character in s, at most k times.
5    public boolean canConvertString(String s, String t, int k) {
6        // Return false if the lengths of the strings are different.
7        if (s.length() != t.length()) {
8            return false;
9        }
10
11        // Array to keep track of how many shifts for each letter are required.
12        int[] shiftCounts = new int[26];
13      
14        // Calculate the shift required for each character to match the target string.
15        for (int i = 0; i < s.length(); ++i) {
16            int shift = (t.charAt(i) - s.charAt(i) + 26) % 26;
17            ++shiftCounts[shift];
18        }
19
20        // Check for each shift if it's possible within the allowed maximum of k shifts.
21        for (int i = 1; i < 26; ++i) {
22            // If the maximum shift needed for any character is more than k, return false.
23            if (i + 26 * (shiftCounts[i] - 1) > k) {
24                return false;
25            }
26        }
27
28        // If all shifts are possible within the allowed maximum, return true.
29        return true;
30    }
31}
32
1class Solution {
2public:
3    bool canConvertString(string source, string target, int maxShifts) {
4        // If the lengths of source and target are not the same, then conversion is not possible
5        if (source.size() != target.size()) {
6            return false;
7        }
8      
9        // Initialize an array to count the number of times a particular shift is needed
10        int shiftCount[26] = {}; // There are 26 possible shifts (for 26 letters)
11
12        // Iterate over the characters of the strings
13        for (int i = 0; i < source.size(); ++i) {
14            // Calculate the shift needed to convert source[i] to target[i]
15            // % 26 ensures the shift is in the range [0, 25]
16            // +26 before % 26 takes care of negative shifts, turning them positive
17            int shift = (target[i] - source[i] + 26) % 26;
18            // Increment the count of the shift needed
19            ++shiftCount[shift];
20        }
21
22        // Iterate over all possible shifts except 0 (no shift needed)
23        for (int i = 1; i < 26; ++i) {
24            // Check if the number of shifts 'i' can be performed within the maxShifts
25            // This considers every 26th shift because the same letter can't be shifted until 26 others have occurred
26            if (i + 26 * (shiftCount[i] - 1) > maxShifts) {
27                return false; // If not possible, return false
28            }
29        }
30
31        // If all shifts can be performed, return true
32        return true;
33    }
34};
35
1function canConvertString(source: string, target: string, maxShifts: number): boolean {
2    // If the lengths of source and target are not the same, then conversion is not possible
3    if (source.length !== target.length) {
4        return false;
5    }
6  
7    // Initialize an array to count the number of times a particular shift is needed
8    // There are 26 possible shifts (for 26 letters in the alphabet)
9    let shiftCount: number[] = new Array(26).fill(0);
10
11    // Iterate over the characters of the strings
12    for (let i = 0; i < source.length; i++) {
13        // Calculate the shift needed to convert source[i] to target[i]
14        // % 26 ensures the shift is in the range [0, 25]
15        // Adding 26 before % 26 takes care of negative shifts by making them positive
16        let shift = (target.charCodeAt(i) - source.charCodeAt(i) + 26) % 26;
17        // Increment the count of the shift needed
18        shiftCount[shift]++;
19    }
20
21    // Iterate over all possible shifts except 0 (no shift needed)
22    for (let i = 1; i < 26; i++) {
23        // Check if the number of shifts 'i' can be performed within the maxShifts
24        // This considers every 26th shift because the same letter can't be shifted again until 26 other shifts have occurred
25        if (i + 26 * (shiftCount[i] - 1) > maxShifts) {
26            return false; // If not possible, return false
27        }
28    }
29
30    // If all shifts can be performed given the constraints, return true
31    return true;
32}
33
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is a min heap?

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the strings s and t. This is because there is a single loop that iterates over the characters of s and t only once, and the operations within the loop are of constant time. The second loop is not dependent on n and iterates up to a constant value (26), which does not affect the time complexity in terms of n.

The space complexity of the code is O(1), as there is a fixed-size integer array cnt of size 26, which does not scale with the input size. The rest of the variables use constant space as well.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫