Rearrange K Substrings to Form Target String - Video Solutions
3365. Rearrange K Substrings to Form Target String | HashMap
Rearrange K Substrings to Form Target String - Video Solution
Watch 8 video solutions for Rearrange K Substrings to Form Target String, a medium level problem involving Hash Table, String, Sorting. This walkthrough by Aryan Mittal has 679 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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
sinto 2 substrings of length 2:["ab", "cd"]. - Rearranging these substrings as
["cd", "ab"], and then concatenating them results in"cdab", which matchest.
Example 2:
Input: s = "aabbcc", t = "bbaacc", k = 3
Output: true
Explanation:
- Split
sinto 3 substrings of length 2:["aa", "bb", "cc"]. - Rearranging these substrings as
["bb", "aa", "cc"], and then concatenating them results in"bbaacc", which matchest.
Example 3:
Input: s = "aabbcc", t = "bbaacc", k = 2
Output: false
Explanation:
- Split
sinto 2 substrings of length 3:["aab", "bcc"]. - These substrings cannot be rearranged to form
t = "bbaacc", so the output isfalse.
Constraints:
1 <= s.length == t.length <= 2 * 1051 <= k <= s.lengths.lengthis divisible byk.sandtconsist only of lowercase English letters.- The input is generated such that
sandtare anagrams of each other.
Approach Overview
Problem Overview: You are given two strings s and target and an integer k. Split both strings into k equal-length substrings. Determine whether rearranging the k substrings from s can form the exact sequence of substrings in target.
Approach 1: Check Permutation of Substrings (O(n log k) time, O(k * m) space)
Divide both s and target into k blocks of length m = n / k. Store the substrings from s in a list or hash table. Do the same for target. The key observation: the multiset of substrings must be identical for a valid rearrangement. You can either sort both substring arrays and compare them or maintain a frequency map where each substring increments or decrements a counter. Sorting costs O(k log k) comparisons while substring creation costs O(n), giving overall O(n log k) time. Space usage is O(k * m) to store the substrings. This method is straightforward and mirrors a classic permutation check using string slices.
Approach 2: Validate Character Distribution with Signatures (O(n) time, O(k) space)
Instead of storing raw substrings, compute a compact signature for each block. Iterate through s in segments of size m, build a 26-length character frequency array for each segment, and convert it to a hashable representation. Store counts of these signatures in a map. Repeat the process for target but decrement the counts. If every signature balances to zero, the rearrangement is valid. Each character is processed exactly once, giving O(n) time complexity. Space remains O(k) for the frequency map. This approach relies heavily on hash table lookups and avoids substring sorting.
Recommended for interviews: Start with the substring permutation check because it directly models the problem and demonstrates understanding of partitioning and multiset comparison. Then optimize with the frequency-signature technique. Interviewers typically expect the hash-based approach since it removes sorting overhead and runs in linear time while still using simple data structures like maps and arrays.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Check Permutation of Substrings | O(n log k) | O(k * m) | Simple implementation when substring comparison or sorting is acceptable |
| Validate Character Distribution with Signatures | O(n) | O(k) | Optimal approach when minimizing sorting overhead and using hash maps |