Scale Engineer

Can Convert String in K Moves

Med
#1419Time: O(N), where N is the length of the strings. The first loop iterates N times to populate the map. The second loop iterates at most 25 times (for each possible shift value from 1 to 25). Thus, the complexity is dominated by the first loop.Space: O(N), where N is the length of the strings. In the worst-case scenario, the `HashMap` might need to store all N indices if they all require a shift (e.g., `s="aaa"`, `t="bbb"`).1 company
Data structures
Hash TableString
Companies
Infosys

Prompt

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.

 

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^5
  • 0 <= k <= 10^9
  • s, t contain only lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves calculating the required circular shift for each character pair (s[i], t[i]). We then group the indices based on their required shift value. For each group that requires a shift d, we determine the sequence of moves needed. Since each index must be used with a unique move number, if a shift d is required for p different indices, we must use p distinct moves that are all congruent to d modulo 26. The smallest such moves are d, d+26, d+52, ..., d+(p-1)*26. We must check if the largest of these required moves is within the given limit k. If this condition holds for all required shifts, the conversion is possible.

Algorithm

  • If s.length() != t.length(), return false.
  • Initialize a HashMap<Integer, List<Integer>> shiftMap.
  • Iterate i from 0 to s.length() - 1:
    • Calculate shift = (t.charAt(i) - s.charAt(i) + 26) % 26.
    • If shift > 0, add the index i to the list associated with the key shift in shiftMap.
  • Iterate through each entry (d, indices) in shiftMap:
    • Let p = indices.size().
    • Calculate the largest move needed for this shift: max_move_needed = d + (long)(p - 1) * 26.
    • If max_move_needed > k, return false.
  • If the loop completes, return true.

Walkthrough

First, we handle the base case: if the lengths of s and t are not equal, conversion is impossible, so we return false.

We use a HashMap<Integer, List<Integer>> where keys are the required shift values (1-25) and values are lists of indices that need that specific shift.

We iterate from i = 0 to s.length() - 1. For each index i, we calculate the necessary shift d to transform s[i] to t[i]. The formula for the shift is d = (t.charAt(i) - s.charAt(i) + 26) % 26.

  • If d is 0, s[i] already equals t[i], so no move is needed for this index.
  • If d is greater than 0, we add the index i to the list associated with the shift d in our HashMap.

After populating the map, we iterate through each entry. For each shift d and its corresponding list of indices of size p:

  • We need p unique moves. The smallest available moves that result in a shift of d are d, d + 26, d + 52, ....
  • To accommodate all p indices, the largest move we'll need is d + (p - 1) * 26.
  • We check if this largest required move exceeds k. If it does, we don't have enough moves, so we return false.

If we successfully check all required shifts without exceeding k, it means the conversion is possible, and we return true.

import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map; class Solution {    public boolean canConvertString(String s, String t, int k) {        if (s.length() != t.length()) {            return false;        }         Map<Integer, List<Integer>> shiftMap = new HashMap<>();        for (int i = 0; i < s.length(); i++) {            int shift = (t.charAt(i) - s.charAt(i) + 26) % 26;            if (shift > 0) {                shiftMap.computeIfAbsent(shift, key -> new ArrayList<>()).add(i);            }        }         for (Map.Entry<Integer, List<Integer>> entry : shiftMap.entrySet()) {            int shift = entry.getKey();            int count = entry.getValue().size();            long maxMoveNeeded = (long)shift + (long)(count - 1) * 26;            if (maxMoveNeeded > k) {                return false;            }        }         return true;    }}

Complexity

Time

O(N), where N is the length of the strings. The first loop iterates N times to populate the map. The second loop iterates at most 25 times (for each possible shift value from 1 to 25). Thus, the complexity is dominated by the first loop.

Space

O(N), where N is the length of the strings. In the worst-case scenario, the `HashMap` might need to store all N indices if they all require a shift (e.g., `s="aaa"`, `t="bbb"`).

Trade-offs

Pros

  • Conceptually straightforward: group by requirement, then check feasibility for each group.

  • Correctly solves the problem.

Cons

  • Uses O(N) extra space to store the indices, which is unnecessary as only the count of indices per shift is required.

  • Slightly more complex implementation due to managing a HashMap of lists compared to a simple frequency array.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem