1540. Can Convert String in K Moves
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
byi
positions in the alphabet, where1 <= 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
.
Solution Approach
The implementation of the solution involves a few key steps that use simple data structures and algorithms.
-
Length Check: First, we check if
s
andt
are of equal length. If not, returnFalse
immediately because the problem states that only characters ins
can be shifted, implying both strings must be of the same length to be convertible. -
Frequency Array: We create an array,
cnt
, of length 26 initialized to zero, which will hold the frequency of each shift amount required. -
Calculate Shifts: We loop over the characters of
s
andt
simultaneously using Python'szip
function. For each corresponding pair of characters(a, b)
, we calculate the shift required to turna
intob
. The shift is calculated using the formula(ord(b) - ord(a) + 26) % 26
, whereord()
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 whereb
comes beforea
in the alphabet. -
Count the Shifts: We increment the count of the appropriate shift amount in the
cnt
array. If no shift is needed, the increment occurs atcnt[0]
. -
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 amounti
, we find out how late this shift can occur by multiplying the number of full cycles(cnt[i] - 1)
by the cycle length26
, and adding the shift amounti
itself. The result tells us at which move number the last shift could feasibly happen. If this move number is greater thank
, the transformation is not possible within the move limit, so we returnFalse
. -
Result: If none of the calculated shift timings exceed
k
, then it is verified that all characters froms
can be shifted to matcht
within the move limit. Thus, the function returnsTrue
.
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a simple example:
s
="abc"
t
="bcd"
k
=2
Step 1: Length Check
- Both strings
s
andt
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
andt
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
.
- Shift for 'a' to 'b' is
Step 4: Count the Shifts
- For each shift calculated, increment the corresponding index in
cnt
:- For shift 1:
cnt[1]
becomes3
because we need to shift by 1 three times.
- For shift 1:
Step 5: Move Validation
- We iterate through
cnt
starting from index 1:- For shift amount
i = 1
and frequencycnt[1] = 3
, calculate maximum move needed:i + 26 * (cnt[1] - 1) = 1 + 26 * (3 - 1) = 53
which exceedsk = 2
, implying that it's impossible to conduct all required shifts withink
moves.
- For shift amount
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
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.
Which of the following problems can be solved with backtracking (select multiple)
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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 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
Want a Structured Path to Master System Design Too? Don’t Miss This!