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 Table String

Companies

Infosys

Prompt

Given two strings s and t, your goal is to convert s into t in k moves or less.

During the i^th (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.

1import java.util.ArrayList;2import java.util.HashMap;3import java.util.List;4import java.util.Map;5 6class Solution {7    public boolean canConvertString(String s, String t, int k) {8        if (s.length() != t.length()) {9            return false;10        }11 12        Map<Integer, List<Integer>> shiftMap = new HashMap<>();13        for (int i = 0; i < s.length(); i++) {14            int shift = (t.charAt(i) - s.charAt(i) + 26) % 26;15            if (shift > 0) {16                shiftMap.computeIfAbsent(shift, key -> new ArrayList<>()).add(i);17            }18        }19 20        for (Map.Entry<Integer, List<Integer>> entry : shiftMap.entrySet()) {21            int shift = entry.getKey();22            int count = entry.getValue().size();23            long maxMoveNeeded = (long)shift + (long)(count - 1) * 26;24            if (maxMoveNeeded > k) {25                return false;26            }27        }28 29        return true;30    }31}

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.

This approach optimizes the previous one by realizing that we don't need to store the actual indices that require a certain shift. All we need is the count of indices for each required shift. By counting the occurrences of each necessary shift d, we can directly calculate the largest move number required for that shift without storing all the indices. This reduces the space complexity from linear to constant.

Algorithm

If s.length() != t.length(), return false.
Initialize an integer array counts of size 26 to all zeros.
Iterate i from 0 to s.length() - 1:
- Calculate shift = (t.charAt(i) - s.charAt(i) + 26) % 26.
- Increment counts[shift].
Iterate d from 1 to 25:
- If counts[d] > 0:
  - Let p = counts[d].
  - Calculate max_move_needed = d + (long)(p - 1) * 26.
  - If max_move_needed > k, return false.
If the loop completes, return true.

Walkthrough

The core logic remains the same: for a shift d needed p times, the largest move required will be d + (p-1)*26. We must verify this is at most k.

Instead of a HashMap storing lists of indices, we use a simple integer array, say counts, of size 26. counts[d] will store the number of times a shift of d is required.

We start by checking if s and t have the same length. If not, we return false.
We iterate through the strings from i = 0 to s.length() - 1.
- For each index i, we compute the required shift d = (t.charAt(i) - s.charAt(i) + 26) % 26.
- We then increment counts[d].
After counting all required shifts, we iterate through our counts array from d = 1 to 25 (as a shift of 0 requires no action).
- For each d, if counts[d] is greater than 0, it means we need to perform a shift of d for counts[d] characters.
- The largest move for this shift d will be d + (counts[d] - 1) * 26.
- We check if this value is greater than k. If it is, we immediately know the conversion is impossible and return false.
If we iterate through all possible shifts (1 to 25) and the condition is never violated, it means we can find a valid move for every required character change within the k limit. We return true.

1class Solution {2    public boolean canConvertString(String s, String t, int k) {3        if (s.length() != t.length()) {4            return false;5        }6 7        int[] counts = new int[26];8        for (int i = 0; i < s.length(); i++) {9            int shift = (t.charAt(i) - s.charAt(i) + 26) % 26;10            counts[shift]++;11        }12 13        for (int d = 1; d < 26; d++) {14            if (counts[d] > 0) {15                long maxMoveNeeded = (long)d + (long)(counts[d] - 1) * 26;16                if (maxMoveNeeded > k) {17                    return false;18                }19            }20        }21 22        return true;23    }24}

Complexity

Time

O(N), where N is the length of the strings. We iterate through the strings once (O(N)) and then iterate through the `counts` array which is of fixed size 26 (O(1)). The total time complexity is O(N).

Space

O(1), as we only use an integer array of fixed size 26, which is constant space and does not depend on the input string length.

Trade-offs

Pros

Optimal time complexity of O(N).
Optimal space complexity of O(1).
Simple and clean implementation using a basic array.

Cons

There are no significant cons to this approach as it is optimal for the given constraints.

Solutions

Solution

1class Solution {2public3  boolean canConvertString(String s, String t, int k) {4    if (s.length() != t.length()) {5      return false;6    }7    int[] cnt = new int[26];8    for (int i = 0; i < s.length(); ++i) {9      int x = (t.charAt(i) - s.charAt(i) + 26) % 26;10      ++cnt[x];11    }12    for (int i = 1; i < 26; ++i) {13      if (i + 26 * (cnt[i] - 1) > k) {14        return false;15      }16    }17    return true;18  }19}

1class Solution {2public:3  bool canConvertString(string s, string t, int k) {4    if (s.size() != t.size()) {5      return false;6    }7    int cnt[26]{};8    for (int i = 0; i < s.size(); ++i) {9      int x = (t[i] - s[i] + 26) % 26;10      ++cnt[x];11    }12    for (int i = 1; i < 26; ++i) {13      if (i + 26 * (cnt[i] - 1) > k) {14        return false;15      }16    }17    return true;18  }19};

1class Solution:2    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

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 problem