Rearrange K Substrings to Form Target String

Med

#2990Time: `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)`.

Algorithms

Sorting

Data structures

Hash Table String

Prompt

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 * 10⁵
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

2 approaches with complexity analysis and trade-offs.

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.

Algorithm

1. Calculate the substring length subLen = s.length() / k.
1. Create an empty list s_substrings.
1. Split s into k substrings of length subLen and add them to s_substrings.
1. Create an empty list t_substrings.
1. Split t into k substrings of length subLen and add them to t_substrings.
1. Sort the s_substrings list.
1. Sort the t_substrings list.
1. Return true if the sorted lists are identical, otherwise return false.

Walkthrough

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:

Calculate the length of each of the k substrings: subLen = s.length() / k.
Create two lists, s_subs and t_subs.
Iterate through s and t with a step size of subLen, extracting each substring and adding it to the respective list.
Sort both s_subs and t_subs lexicographically.
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.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5class Solution {6    public boolean canRearrange(String s, String t, int k) {7        int n = s.length();8        // The problem guarantees s.length() is divisible by k.9        int subLen = n / k;10 11        List<String> s_subs = new ArrayList<>(k);12        for (int i = 0; i < n; i += subLen) {13            s_subs.add(s.substring(i, i + subLen));14        }15 16        List<String> t_subs = new ArrayList<>(k);17        for (int i = 0; i < n; i += subLen) {18            t_subs.add(t.substring(i, i + subLen));19        }20 21        Collections.sort(s_subs);22        Collections.sort(t_subs);23 24        return s_subs.equals(t_subs);25    }26}

Complexity

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)`.

Trade-offs

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.

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.

Algorithm

1. Calculate the substring length subLen = s.length() / k.
1. Create a hash map sub_counts to store substring frequencies.
1. Iterate through s, splitting it into substrings of length subLen. For each substring, increment its count in sub_counts.
1. 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.
1. If the loop completes, return true.

Walkthrough

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:

Calculate the substring length subLen = s.length() / k.
Create a HashMap<String, Integer> to store the frequency of each unique substring found in s.
Iterate through s, slicing it into substrings of length subLen. For each substring, increment its count in the hash map.
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'.
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.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public boolean canRearrange(String s, String t, int k) {6        int n = s.length();7        // The problem guarantees s.length() is divisible by k.8        int subLen = n / k;9 10        Map<String, Integer> subCounts = new HashMap<>();11        for (int i = 0; i < n; i += subLen) {12            String sub = s.substring(i, i + subLen);13            subCounts.put(sub, subCounts.getOrDefault(sub, 0) + 1);14        }15 16        for (int i = 0; i < n; i += subLen) {17            String sub = t.substring(i, i + subLen);18            Integer count = subCounts.get(sub);19            if (count == null || count == 0) {20                return false;21            }22            subCounts.put(sub, count - 1);23        }24 25        return true;26    }27}

Complexity

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

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  boolean isPossibleToRearrange(String s, String t, int k) {4    Map<String, Integer> cnt = new HashMap<>(k);5    int n = s.length();6    int m = n / k;7    for (int i = 0; i < n; i += m) {8      cnt.merge(s.substring(i, i + m), 1, Integer : : sum);9      cnt.merge(t.substring(i, i + m), -1, Integer : : sum);10    }11    for (int v : cnt.values()) {12      if (v != 0) {13        return false;14      }15    }16    return true;17  }18}

1class Solution {2public:3  bool isPossibleToRearrange(string s, string t, int k) {4    unordered_map<string, int> cnt;5    int n = s.size();6    int m = n / k;7    for (int i = 0; i < n; i += m) {8      cnt[s.substr(i, m)]++;9      cnt[t.substr(i, m)]--;10    }11    for (auto &[_, v] : cnt) {12      if (v) {13        return false;14      }15    }16    return true;17  }18};

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

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

Solution

1class Solution {2public3  boolean isPossibleToRearrange(String s, String t, int k) {4    Map<String, Integer> cnt = new HashMap<>(k);5    int n = s.length();6    int m = n / k;7    for (int i = 0; i < n; i += m) {8      cnt.merge(s.substring(i, i + m), 1, Integer : : sum);9      cnt.merge(t.substring(i, i + m), -1, Integer : : sum);10    }11    for (int v : cnt.values()) {12      if (v != 0) {13        return false;14      }15    }16    return true;17  }18}

1class Solution {2public:3  bool isPossibleToRearrange(string s, string t, int k) {4    unordered_map<string, int> cnt;5    int n = s.size();6    int m = n / k;7    for (int i = 0; i < n; i += m) {8      cnt[s.substr(i, m)]++;9      cnt[t.substr(i, m)]--;10    }11    for (auto &[_, v] : cnt) {12      if (v) {13        return false;14      }15    }16    return true;17  }18};

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

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.