Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Move from brute-force thinking to an efficient approach using hash map strategy.
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:
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.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 1:
Input: s = "input", t = "ouput", k = 9 Output: true Explanation: In the 6th move, we shift 'i' 6 times to get 'o'. And in the 7th move we shift 'n' to get 'u'.
Example 2:
Input: s = "abc", t = "bcd", k = 10 Output: false Explanation: We need to shift each character in s one time to convert it into t. We can shift 'a' to 'b' during the 1st move. However, there is no way to shift the other characters in the remaining moves to obtain t from s.
Example 3:
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:
1 <= s.length, t.length <= 10^50 <= k <= 10^9s, t contain only lowercase English letters.Problem summary: 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: 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. 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map
"input" "ouput" 9
"abc" "bcd" 10
"aab" "bbb" 27
minimum-cost-to-convert-string-i)minimum-cost-to-convert-string-ii)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1540: Can Convert String in K Moves
class Solution {
public boolean canConvertString(String s, String t, int k) {
if (s.length() != t.length()) {
return false;
}
int[] cnt = new int[26];
for (int i = 0; i < s.length(); ++i) {
int x = (t.charAt(i) - s.charAt(i) + 26) % 26;
++cnt[x];
}
for (int i = 1; i < 26; ++i) {
if (i + 26 * (cnt[i] - 1) > k) {
return false;
}
}
return true;
}
}
// Accepted solution for LeetCode #1540: Can Convert String in K Moves
func canConvertString(s string, t string, k int) bool {
if len(s) != len(t) {
return false
}
cnt := [26]int{}
for i := range s {
x := (t[i] - s[i] + 26) % 26
cnt[x]++
}
for i := 1; i < 26; i++ {
if i+26*(cnt[i]-1) > k {
return false
}
}
return true
}
# Accepted solution for LeetCode #1540: Can Convert String in K Moves
class Solution:
def canConvertString(self, s: str, t: str, k: int) -> bool:
if len(s) != len(t):
return False
cnt = [0] * 26
for a, b in zip(s, t):
x = (ord(b) - ord(a) + 26) % 26
cnt[x] += 1
for i in range(1, 26):
if i + 26 * (cnt[i] - 1) > k:
return False
return True
// Accepted solution for LeetCode #1540: Can Convert String in K Moves
struct Solution;
use std::collections::HashMap;
impl Solution {
fn can_convert_string(s: String, t: String, k: i32) -> bool {
let n = s.len();
let m = t.len();
if n != m {
return false;
}
let s: Vec<i32> = s.bytes().map(|b| (b - b'a') as i32).collect();
let t: Vec<i32> = t.bytes().map(|b| (b - b'a') as i32).collect();
let mut count: HashMap<i32, i32> = HashMap::new();
for i in 0..n {
if s[i] == t[i] {
continue;
}
*count.entry((26 + t[i] - s[i]) % 26).or_default() += 1;
}
let mut max = 0;
for (k, v) in count {
max = max.max((v - 1) * 26 + k);
}
max <= k
}
}
#[test]
fn test() {
let s = "input".to_string();
let t = "ouput".to_string();
let k = 9;
let res = true;
assert_eq!(Solution::can_convert_string(s, t, k), res);
let s = "abc".to_string();
let t = "bcd".to_string();
let k = 10;
let res = false;
assert_eq!(Solution::can_convert_string(s, t, k), res);
let s = "aab".to_string();
let t = "bbb".to_string();
let k = 27;
let res = true;
assert_eq!(Solution::can_convert_string(s, t, k), res);
}
// Accepted solution for LeetCode #1540: Can Convert String in K Moves
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #1540: Can Convert String in K Moves
// class Solution {
// public boolean canConvertString(String s, String t, int k) {
// if (s.length() != t.length()) {
// return false;
// }
// int[] cnt = new int[26];
// for (int i = 0; i < s.length(); ++i) {
// int x = (t.charAt(i) - s.charAt(i) + 26) % 26;
// ++cnt[x];
// }
// for (int i = 1; i < 26; ++i) {
// if (i + 26 * (cnt[i] - 1) > k) {
// return false;
// }
// }
// return true;
// }
// }
Use this to step through a reusable interview workflow for this problem.
For each element, scan the rest of the array looking for a match. Two nested loops give n × (n−1)/2 comparisons = O(n²). No extra space since we only use loop indices.
One pass through the input, performing O(1) hash map lookups and insertions at each step. The hash map may store up to n entries in the worst case. This is the classic space-for-time tradeoff: O(n) extra memory eliminates an inner loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.