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:
s into 2 substrings of length 2: ["ab", "cd"].["cd", "ab"], and then concatenating them results in "cdab", which matches t.Example 2:
Input: s = "aabbcc", t = "bbaacc", k = 3
Output: true
Explanation:
s into 3 substrings of length 2: ["aa", "bb", "cc"].["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:
s into 2 substrings of length 3: ["aab", "bcc"].t = "bbaacc", so the output is false.Constraints:
1 <= s.length == t.length <= 2 * 1051 <= k <= s.lengths.length is divisible by k.s and t consist only of lowercase English letters.s and t are anagrams of each other.In #3365 Rearrange K Substrings to Form Target String, the key idea is to determine whether the source string can be partitioned into k equal-sized substrings and rearranged so that their concatenation forms the target string. Since rearrangement does not change substring content, the focus shifts to verifying whether both strings produce the same multiset of substrings.
First, validate that the two strings have the same length and that the length is divisible by k. Compute the substring length as len / k, then split both strings into chunks of that size. Using a hash map (frequency map), count how many times each substring appears in the source string. Next, iterate through the target string’s chunks and decrement the corresponding counts.
If all counts match and the map becomes empty, the rearrangement is possible. This approach efficiently compares substring distributions without exploring permutations.
Time Complexity: O(n) for scanning and hashing substrings. Space Complexity: O(k) for storing substring frequencies.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash map with fixed-size substring partitioning | O(n) | O(k) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Split <code>s</code> into <code>k</code> equal-sized substrings, use a map to track frequencies, and check if rearranging them can form <code>t</code>.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Splitting the string into k equal parts ensures that rearrangement only occurs at the substring level rather than at individual characters. This constraint defines the structure of the solution and allows substring frequency comparison instead of full permutation checks.
Problems involving substring partitioning, hashing, and frequency counting are common in FAANG-style interviews. While the exact problem may vary, similar concepts like string chunking, anagram grouping, and hash map comparisons frequently appear in coding rounds.
A hash map is the most suitable data structure because it efficiently tracks the frequency of each substring. By incrementing counts for substrings from the source and decrementing them for the target, you can quickly verify whether both strings contain identical substring sets.
The optimal approach is to divide both strings into k equal-length substrings and compare their frequency distributions using a hash map. If every substring in the source string appears the same number of times in the target string, the rearrangement is possible. This avoids generating permutations and keeps the solution efficient.