# Rearrange K Substrings to Form Target String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/rearrange-k-substrings-to-form-target-string)
Canonical: https://scaleengineer.com/dsa/problems/rearrange-k-substrings-to-form-target-string
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Hash Table, String
---
## Problem
You are given two strings `s` and `t`, both of which are anagrams of each other, and an integer `k`.

Your task is to determine whether it is possible to split the string `s` into `k` equal-sized substrings, rearrange the substrings, and concatenate them in _any order_ to create a new string that matches the given string `t`.

Return `true` if this is possible, otherwise, return `false`.

An **anagram** is a word or phrase formed by rearranging the letters of a different word or phrase, using all the original letters exactly once.

A **substring** is a contiguous **non-empty** sequence of characters within a string.

**Example 1:**

**Input:** s = "abcd", t = "cdab", k = 2

**Output:** true

**Explanation:**

* Split `s` into 2 substrings of length 2: `["ab", "cd"]`.
* Rearranging these substrings as `["cd", "ab"]`, and then concatenating them results in `"cdab"`, which matches `t`.

**Example 2:**

**Input:** s = "aabbcc", t = "bbaacc", k = 3

**Output:** true

**Explanation:**

* Split `s` into 3 substrings of length 2: `["aa", "bb", "cc"]`.
* Rearranging these substrings as `["bb", "aa", "cc"]`, and then concatenating them results in `"bbaacc"`, which matches `t`.

**Example 3:**

**Input:** s = "aabbcc", t = "bbaacc", k = 2

**Output:** false

**Explanation:**

* Split `s` into 2 substrings of length 3: `["aab", "bcc"]`.
* These substrings cannot be rearranged to form `t = "bbaacc"`, so the output is `false`.

**Constraints:**

* `1 <= s.length == t.length <= 2 * 105`
* `1 <= k <= s.length`
* `s.length` is divisible by `k`.
* `s` and `t` consist only of lowercase English letters.
* The input is generated such that `s` and `t` are anagrams of each other.

# Approaches
## Sorting-Based Comparison of Substrings
This approach tackles the problem by treating the substrings from `s` and `t` as two multisets. The core idea is that if two multisets are identical, their sorted versions will also be identical. We generate the substrings for both `s` and `t`, sort them, and then perform a direct comparison.
**Time:** `O(n * log(k))`, where `n` is the length of the strings and `k` is the number of substrings. Generating the substrings takes `O(n)`. Sorting a list of `k` strings, where each string comparison takes `O(n/k)`, results in a total sorting time of `O(k * log(k) * (n/k)) = O(n * log(k))`. · **Space:** `O(n)`. We need two lists to store the substrings. Each list contains `k` substrings of length `n/k`, so the total space required is `2 * k * (n/k) = O(n)`.
**Pros:** Conceptually simple and relies on standard sorting and comparison logic.; Easy to implement using built-in list and sorting functionalities.
**Cons:** The time complexity is dominated by sorting, making it less efficient than a hash-based approach.; Requires storing all substrings for both `s` and `t` in memory, leading to `O(n)` space usage.
### Explanation
The problem asks if the multiset of `k` substrings from `s` can be rearranged to form `t`. This is equivalent to checking if the multiset of substrings from `s` is identical to the multiset of substrings from `t`.
A straightforward way to compare two multisets is to convert them to sorted lists and check for equality.
The algorithm proceeds as follows:
1.  Calculate the length of each of the `k` substrings: `subLen = s.length() / k`.
2.  Create two lists, `s_subs` and `t_subs`.
3.  Iterate through `s` and `t` with a step size of `subLen`, extracting each substring and adding it to the respective list.
4.  Sort both `s_subs` and `t_subs` lexicographically.
5.  Finally, compare the two sorted lists. If they are equal, it means `s` and `t` are composed of the same substrings, and we return `true`. Otherwise, we return `false`.
```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public boolean canRearrange(String s, String t, int k) {
        int n = s.length();
        // The problem guarantees s.length() is divisible by k.
        int subLen = n / k;

        List<String> s_subs = new ArrayList<>(k);
        for (int i = 0; i < n; i += subLen) {
            s_subs.add(s.substring(i, i + subLen));
        }

        List<String> t_subs = new ArrayList<>(k);
        for (int i = 0; i < n; i += subLen) {
            t_subs.add(t.substring(i, i + subLen));
        }

        Collections.sort(s_subs);
        Collections.sort(t_subs);

        return s_subs.equals(t_subs);
    }
}
```
### Algorithm
- 1. Calculate the substring length `subLen = s.length() / k`.
- 2. Create an empty list `s_substrings`.
- 3. Split `s` into `k` substrings of length `subLen` and add them to `s_substrings`.
- 4. Create an empty list `t_substrings`.
- 5. Split `t` into `k` substrings of length `subLen` and add them to `t_substrings`.
- 6. Sort the `s_substrings` list.
- 7. Sort the `t_substrings` list.
- 8. Return `true` if the sorted lists are identical, otherwise return `false`.

## Frequency Map (HashMap) of Substrings
This optimized approach uses a hash map to efficiently count the frequencies of substrings. It first builds a frequency map for all substrings of `s`. Then, it iterates through the substrings of `t`, checking if each one can be 'accounted for' by the map. This avoids the overhead of sorting.
**Time:** `O(n)`, where `n` is the string length. Building the map requires iterating through `s`, which involves `k` substring extractions and hash map operations. Each operation takes `O(n/k)` on average (for hashing the substring), leading to a total of `k * O(n/k) = O(n)`. The verification loop for `t` similarly takes `O(n)`. · **Space:** `O(n)`. In the worst case, all `k` substrings of `s` are distinct. The hash map must store these `k` keys, each of length `n/k`. The total space for the keys is `k * (n/k) = n`.
**Pros:** Optimal time complexity of `O(n)`, which is faster than the sorting-based approach.; Can terminate early as soon as a mismatch is found, potentially saving computation on large inputs.
**Cons:** While asymptotically faster, hash map operations can have higher constant-factor overheads than array/list operations.; Still requires `O(n)` space in the worst-case scenario where all substrings are unique.
### Explanation
This method also relies on the principle of comparing the multisets of substrings from `s` and `t`. However, it uses a hash map for a more efficient comparison.
The algorithm is as follows:
1.  Calculate the substring length `subLen = s.length() / k`.
2.  Create a `HashMap<String, Integer>` to store the frequency of each unique substring found in `s`.
3.  Iterate through `s`, slicing it into substrings of length `subLen`. For each substring, increment its count in the hash map.
4.  Iterate through `t`, also slicing it into substrings. For each substring from `t`:
    -   Check if the substring exists as a key in the map with a count greater than zero.
    -   If it doesn't, it means `t` contains a substring not available in `s` (or not enough copies of it), so we return `false`.
    -   If it does, we decrement its count in the map to signify that one instance has been 'used'.
5.  If the loop over `t`'s substrings completes successfully, it means every substring in `t` was matched with one from `s`. Since the total number of substrings is the same, the multisets must be identical. We can then return `true`.
```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean canRearrange(String s, String t, int k) {
        int n = s.length();
        // The problem guarantees s.length() is divisible by k.
        int subLen = n / k;

        Map<String, Integer> subCounts = new HashMap<>();
        for (int i = 0; i < n; i += subLen) {
            String sub = s.substring(i, i + subLen);
            subCounts.put(sub, subCounts.getOrDefault(sub, 0) + 1);
        }

        for (int i = 0; i < n; i += subLen) {
            String sub = t.substring(i, i + subLen);
            Integer count = subCounts.get(sub);
            if (count == null || count == 0) {
                return false;
            }
            subCounts.put(sub, count - 1);
        }

        return true;
    }
}
```
### Algorithm
- 1. Calculate the substring length `subLen = s.length() / k`.
- 2. Create a hash map `sub_counts` to store substring frequencies.
- 3. Iterate through `s`, splitting it into substrings of length `subLen`. For each substring, increment its count in `sub_counts`.
- 4. Iterate through `t`, splitting it into substrings of length `subLen`. For each substring `sub_t`:
  - a. Get the current count of `sub_t` from the map.
  - b. If the count is null or zero, return `false`.
  - c. Decrement the count of `sub_t` in the map.
- 5. If the loop completes, return `true`.

# Solutions
### Java

```java
class Solution {
public
  boolean isPossibleToRearrange(String s, String t, int k) {
    Map<String, Integer> cnt = new HashMap<>(k);
    int n = s.length();
    int m = n / k;
    for (int i = 0; i < n; i += m) {
      cnt.merge(s.substring(i, i + m), 1, Integer : : sum);
      cnt.merge(t.substring(i, i + m), -1, Integer : : sum);
    }
    for (int v : cnt.values()) {
      if (v != 0) {
        return false;
      }
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool isPossibleToRearrange(string s, string t, int k) {
    unordered_map<string, int> cnt;
    int n = s.size();
    int m = n / k;
    for (int i = 0; i < n; i += m) {
      cnt[s.substr(i, m)]++;
      cnt[t.substr(i, m)]--;
    }
    for (auto &[_, v] : cnt) {
      if (v) {
        return false;
      }
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def isPossibleToRearrange(self, s: str, t: str, k: int) -> bool: cnt = Counter() n = len(s) m = n // k for i in range(0, n, m): cnt[s[i: i + m]] += 1 cnt[t[i: i + m]] -= 1 return all(v == 0 for v in cnt . values())

```