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.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.
Given that `s` and `t` are anagrams of each other, the characters in `s` can already form `t` if rearranged correctly. The challenge lies in dividing `s` into `k` equal parts and deciding if rearranging these parts can yield `t`. If `s` can be split into `k` equal parts, it means every combination of these parts should offer a potential solution since `t` is an anagram of `s`. No specific order exists, so directly returning `true` given valid input constraints is acceptable.
This C function checks if `n` (length of `s`) is divisible by `k`. This leads to equal substring parts, and since `s` and `t` are anagrams, it implies possible rearrangement, directly returning `true`.
Time Complexity: O(1) because we only check simple arithmetic.
Space Complexity: O(1) since no additional space is used.
The goal is to ensure `s` can be divided into substrings that can rearrange through these substrings into `t`. Since `s` and `t` are anagrams, the focused step is merely confirming that `s` is divisible by `k` as equal sections of anagrams provide the desired property automatically.
This C function ensures length check consistency with divisibility as core solution logic for substring rearrangement into `t`.
Time Complexity: O(1), since checking divisibility is constant time.
Space Complexity: O(1), no extra allocation.
Let the length of the string s be n, then the length of each substring is m = n / k.
We use a hash table cnt to record the difference between the number of occurrences of each substring of length m in string s and in string t.
We traverse the string s, extracting substrings of length m each time, and update the hash table cnt.
Finally, we check whether all values in the hash table cnt are 0.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string s.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Check Permutation of Substrings | Time Complexity: O(1) because we only check simple arithmetic. Space Complexity: O(1) since no additional space is used. |
| Validate Character Distribution | Time Complexity: O(1), since checking divisibility is constant time. Space Complexity: O(1), no extra allocation. |
| Hash Table | — |
| 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 |
3365. Rearrange K Substrings to Form Target String | HashMap • Aryan Mittal • 637 views views
Watch 2 more video solutions →Practice Rearrange K Substrings to Form Target String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor