# Can Convert String in K Moves
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/can-convert-string-in-k-moves)
Canonical: https://scaleengineer.com/dsa/problems/can-convert-string-in-k-moves
**Data structures:** Hash Table, String
**Companies:** [Infosys](https://scaleengineer.com/companies/infosys)
---
## Problem
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
## Grouping Indices by Shift using HashMap
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.
**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"`).
**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.
### Explanation
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`.

```java
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;
    }
}
```
### 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`.

## Optimal Approach using Frequency Counting 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.
**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.
**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.
### Explanation
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`.

```java
class Solution {
    public boolean canConvertString(String s, String t, int k) {
        if (s.length() != t.length()) {
            return false;
        }

        int[] counts = new int[26];
        for (int i = 0; i < s.length(); i++) {
            int shift = (t.charAt(i) - s.charAt(i) + 26) % 26;
            counts[shift]++;
        }

        for (int d = 1; d < 26; d++) {
            if (counts[d] > 0) {
                long maxMoveNeeded = (long)d + (long)(counts[d] - 1) * 26;
                if (maxMoveNeeded > k) {
                    return false;
                }
            }
        }

        return true;
    }
}
```
### 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`.

# Solutions
### Java

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

```

### CPP

```cpp
class Solution {
public:
  bool canConvertString(string s, string t, int k) {
    if (s.size() != t.size()) {
      return false;
    }
    int cnt[26]{};
    for (int i = 0; i < s.size(); ++i) {
      int x = (t[i] - s[i] + 26) % 26;
      ++cnt[x];
    }
    for (int i = 1; i < 26; ++i) {
      if (i + 26 * (cnt[i] - 1) > k) {
        return false;
      }
    }
    return true;
  }
};

```

### Python

```python
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

```