Can Convert String in K Moves Solution In C++/Java/Python/Javascript
Problem Description
Given two strings s and t, your goal is to convert s into t in k moves or less.
During the ith (1 <= i <= k) move you can:
1) Choose any index j (1-indexed) from s, such that 1 <= j <= s.length and j has not been chosen in any previous move, and shift the character at that index i times.
2) Do nothing.
Shifting a character means replacing it by the next letter in the alphabet (wrapping around so that 'z' becomes 'a'). Shifting a character by i means applying the shift operations i times. Remember that any index j can be picked at most once.
Return true if it's possible to convert s into t in no more than k moves, otherwise return false.
Example
Input: s = "abc", t = "bde", k = 8
Output: false
Explanation: Let's compare each character in s and t:
'a' → 'b': The difference is 1. It requires 1 shift.
'b' → 'd': The difference is 2. It requires 2 shifts.
'c' → 'e': The difference is 2. It requires 2 shifts. (but we can’t perform so we wrap around z, so it requires 26 + 2 = 28)
Now, calculate the total shifts needed:
'a' (1 shift) → 'b' (2 shifts) → 'c' (2 shifts).
Since k = 8, which is smaller than the required 28 shifts, it's not possible to convert s into t in k moves.
Hence, returned false.
Input: s = "aab", t = "bbb", k = 27
Output: true
Explanation: In the 1st move, we shift the first 'a' 1 time to get 'b'. In the 27th move, we shift the second 'a' 27 times to get 'b'.
Constraints
- n == gas.length == cost.length
- 1 <= n <= 105
- 0 <= gas[i], cost[i] <= 104
Though this problem might appear complex at first, there are various ways to approach it. You could simulate the shifting process directly, analyze the differences between corresponding characters, or even use modular arithmetic to simplify the calculations. Each method comes with its own trade-offs in terms of computational efficiency and clarity of implementation. So, lets look at Convert String in K Moves solution.
Optimal Approach
Intuition
Since, we need to shift the characters such that same number of shifts can’t be repeated. We could think of storing it in some data structure which tells how many such unique shifts performed. Did you guess? Lets say to move from b → d we need to 2 shifts, similarly for other characters like f → h we can’t move 2 shifts instead we need to move (2 + 26) shifts i.e (t[i] - s[i] + 26) shifts. Because we have to wrap around ‘z’ to make a full circle so we need to move additional 26 steps(total alphabets) plus the difference which is (t[i] - s[i]). Similarly if we get another such difference then we make (t[i] - s[i] + 2 * 26)... and so on.
Approach
Considering the intuition, we can make use of a vector or a map or Hashmap which will store number of times certain kind of shifts performed.
For eg: How many times 4 shifts performed, How many times 5 shifts performed, etc. Lets say 4 shifts already performed 3 times, then next time if such shifts required then we have to make (4 + 3 * 26) shifts to make a change from one character to another.
So in general for nth shifts we require: (diff + n * 26) changes from one character to another to finally change it to required character.
Lets understanding this in good detail,
Step 1: Length Check
If the lengths of s and t are not the same, it's impossible to convert s to t. Return false.
Step 2: Calculate Shifts
For each character in s and t, calculate the minimum number of shifts needed to convert one character into the other:
Formula: diff = (t[i] - s[i] + 26) % 26
t[i] - s[i] calculates the difference in their ASCII values.
Adding 26 ensures the result is non-negative (handles wrapping).
% 26 ensures the shift stays within the alphabet range.
Step 3: Manage Repeated Shifts
Use a data structure (like a map or array) to keep track of how many times each type of shift has been used. If a shift is already used n times, the next occurrence of the same shift will be:
required_shift = diff + n * 26
Step 4: Check Against k
If the required_shift exceeds k, return false. Otherwise, mark this shift as used.
Step 5: Return Result
If all characters can be converted without exceeding k, return true.
Example
Consider: s = “hello” t = “world”
for index i = 0, h → w ⇒ No. of shifts required = t[0] - s[0] = 15 steps
for index i = 1, e → o ⇒ No. of shifts required = t[1] - s[1] = 10 steps
for index i = 2, l → r ⇒ No. of shifts required = 6 steps
for index i = 3, l → l ⇒ No shifts required! (because of same letters)
for index i = 4, o → d ⇒ No. of shifts required = 15 steps (Now, look at this, this steps are getting repeated, hence we can’t perform this as per question, instead we need to wrap around ‘z’ to ‘a’ to reach the final character.)
So, no. of steps required will be (15 + 1 * 26) = 41 steps performed. But before performing we need to check if it is <= K (look at questions requirements).
Ok, now a question for you, what again we get steps requirement of 15 steps do we need to move this steps?? Of course no!! Why?
Dry Run
Initialization:
s = "abc"
t = "def"
k = 10
mp = {}
Iteration 1: i = 0
Characters: s[0] = 'a', t[0] = 'd'
Calculate diff = (t[0] - s[0] + 26) % 26 = ('d' - 'a' + 26) % 26 = (3 + 26) % 26 = 3.
diff = 3 means we need 3 shifts to convert 'a' to 'd'.
Check if this shift is possible:
val = diff + 26 * mp[diff] = 3 + 26 * 0 = 3.
val = 3 is less than or equal to k = 10.
Perform the shift and update mp: mp[3]++ → mp = {3: 1}.
Iteration 2: i = 1
Characters: s[1] = 'b', t[1] = 'e'
Calculate diff = (t[1] - s[1] + 26) % 26 = ('e' - 'b' + 26) % 26 = (3 + 26) % 26 = 3.
Again, diff = 3.
Check if this shift is possible:
val = diff + 26 * mp[diff] = 3 + 26 * 1 = 29.
val = 29 is greater than k = 10.
Since this shift is not possible, the function returns false.
Final Output: Return false because the string s cannot be converted to t within k = 10 moves.
Code for All Languages
C++
class Solution {
public:
// Convert String in K Moves solution in C++
bool canConvertString(string s, string t, int k) {
// unordered-maps/hashmaps to track the number of shifts of each type
unordered_map<int, int> mp;
int n = s.size(), m = t.size();
// if there size is different then we can't make them equal in any ways.
if(n != m) return false;
for(int i = 0; i < n; ++i) {
// character differences, if it goes beyond 26 put it down using % 26
int diff = (t[i] - s[i] + 26) % 26;
// if both t[i] and s[i] is same character then diff will be 0, so we are ignoring it
if(diff == 0) continue;
// shifting character: i, i + 26, i + 2*26, ....
long long val = diff + 26 * mp[diff];
// if such shift/wrapping is possible then increment the count in maps
if(val <= k) mp[diff]++;
else return false; // if no any shifts possible to reach s[i] -> t[i] return false
}
// after iterating above for loop we are very sure that, string is convertible, so we return true
return true;
}
};Java
import java.util.HashMap;
class Solution {
// Convert String in K Moves solution in Java
public boolean canConvertString(String s, String t, int k) {
// HashMap to track the number of shifts of each type
HashMap<Integer, Integer> map = new HashMap<>();
int n = s.length(), m = t.length();
// If their sizes are different, we can't make them equal in any way.
if (n != m) return false;
for (int i = 0; i < n; ++i) {
// Character differences; if it goes beyond 26, normalize it using % 26
int diff = (t.charAt(i) - s.charAt(i) + 26) % 26;
// If both t[i] and s[i] are the same character, then diff will be 0, so we ignore it
if (diff == 0) continue;
// Shifting character: i, i + 26, i + 2*26, ...
long val = diff + 26L * map.getOrDefault(diff, 0);
// If such a shift/wrapping is possible, then increment the count in the map
if (val <= k) {
map.put(diff, map.getOrDefault(diff, 0) + 1);
} else {
return false; // If no shift is possible to reach s[i] -> t[i], return false
}
}
// After iterating the above for loop, we are very sure that the string is convertible, so return true
return true;
}
}Python
class Solution:
# Convert String in K Moves solution in Python
def canConvertString(self, s: str, t: str, k: int) -> bool:
# Dictionary to track the number of shifts of each type
mp = {}
n, m = len(s), len(t)
# If their sizes are different, we can't make them equal in any way
if n != m:
return False
for i in range(n):
# Character differences; if it goes beyond 26, normalize it using % 26
diff = (ord(t[i]) - ord(s[i]) + 26) % 26
# If both t[i] and s[i] are the same character, then diff will be 0, so we ignore it
if diff == 0:
continue
# Shifting character: i, i + 26, i + 2*26, ...
val = diff + 26 * mp.get(diff, 0)
# If such a shift/wrapping is possible, then increment the count in the map
if val <= k:
mp[diff] = mp.get(diff, 0) + 1
else:
return False # If no shift is possible to reach s[i] -> t[i], return False
# After iterating the above for loop, we are very sure that the string is convertible, so return True
return TrueJavascript
class Solution {
// Convert String in K Moves solution in javaScript
canConvertString(s, t, k) {
// Map to track the number of shifts of each type
let mp = new Map();
let n = s.length, m = t.length;
// If their sizes are different, we can't make them equal in any way
if (n !== m) return false;
for (let i = 0; i < n; ++i) {
// Character differences; if it goes beyond 26, normalize it using % 26
let diff = (t.charCodeAt(i) - s.charCodeAt(i) + 26) % 26;
// If both t[i] and s[i] are the same character, then diff will be 0, so we ignore it
if (diff === 0) continue;
// Shifting character: i, i + 26, i + 2*26, ...
let val = diff + 26 * (mp.get(diff) || 0);
// If such a shift/wrapping is possible, then increment the count in the map
if (val <= k) {
mp.set(diff, (mp.get(diff) || 0) + 1);
} else {
return false; // If no shift is possible to reach s[i] -> t[i], return false
}
}
// After iterating the above for loop, we are very sure that the string is convertible, so return true
return true;
}
}Time Complexity: O(n)
Net time complexity:
O(n) => for for loop running till size of string s or t
Others is just assignment of variables like n = s.size(), etc which takes time complexity of O(1)
So, overall: O(N) + O(1) ~ O(N)
Since we are only iterating for loop till size of s or t(both will be of same size during check).
Space Complexity: O(n)
Auxiliary Space complexity, which refers to the extra space used by the algorithm aside from the input. So in our case we are using map using O(N) space. [for map data structure storing till n elements]
Other variable store O(1) space.
So, all in all total Space complexity = O(N) + O(1) ~ O(N) only
Because we are using a map to store no. of time certain shifts performed. So at max it will store frequency for all n elements(in case of unique shifts). Therefore, extra space complexity will be O(N).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Given a 0-indexed binary string boxes and an integer k, perform the following operation exactly k times:
- Select a ball in one box and move it to an adjacent box.
- Each move consumes one operation, and the total number of operations must not exceed k.
Determine the minimum number of operations required to move all balls to each box.
Given a 0-indexed integer array nums and an integer k perform the following operation exactly k times:
- Remove two equal elements or one element from the array.
- Each removal consumes one operation, and the total number of operations must not exceed k.
Determine the minimum number of operations required to make the array empty.