#3365

Medium

LeetCode Problem Workspace

Rearrange K Substrings to Form Target String

Determine if s can be split into k equal substrings and rearranged to match t using a hash table for frequency tracking.

hash table string sorting

Problem Statement

You are given two strings s and t of the same length, and an integer k. Both strings are guaranteed to be anagrams of each other. Your goal is to determine if s can be divided into k equal-length substrings, and those substrings can be rearranged to form t.

Return true if it is possible to reorder the k substrings of s to exactly match t. Otherwise, return false. The solution requires careful handling of substring frequency and order, leveraging hash tables to ensure accuracy and efficiency.

Examples

Example 1

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

Output: true

Example 2

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

Output: true

Example 3

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

Output: 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.

Solution Approach

Split s and t into substrings

Divide s into k equal-length substrings and similarly partition t conceptually. Each substring from s must match a segment in t after rearrangement. Use a consistent length calculation to avoid off-by-one errors.

Use hash maps to count frequencies

Create a hash map for the substrings of s counting how many times each occurs. Then iterate over the corresponding substrings in t to check if the frequency map allows forming t. This avoids full permutation generation.

Validate rearrangement possibility

Check if each substring in t exists in the s frequency map and decrement counts as used. If all substrings can be matched, return true. Otherwise, return false, ensuring you catch any imbalance early for efficiency.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the substring splitting and frequency map operations, roughly O(n) where n is the length of s. Space complexity is O(k) for storing substring counts in the hash map, assuming substring length is constant relative to n.

What Interviewers Usually Probe

Emphasize handling exact k substring partitions and potential off-by-one errors.
Expect discussion of hash table usage to track substring frequencies efficiently.
Be prepared to explain why naive permutation checks would be inefficient for larger n.

Common Pitfalls or Variants

Common pitfalls

Forgetting to check that s.length is divisible by k, causing incorrect substring sizes.
Using a simple sort of substrings without counting frequencies can miss valid rearrangements.
Failing to decrement the hash map counts properly leads to false positives when matching t.

Follow-up variants

Allowing k to be variable instead of fixed, requiring dynamic substring partitioning.
Checking if rearrangement is possible with substrings of unequal length, increasing complexity.
Extending to multi-character alphabets or Unicode strings, affecting hash map size and performance.

FAQ

What is the best approach to solve Rearrange K Substrings to Form Target String?

Split s into k equal substrings and use a hash map to track substring frequencies, then verify t can be formed using these counts.

Can this problem be solved without hash tables?

Technically yes, by generating all permutations, but it is highly inefficient; hash tables optimize frequency checking.

What should I watch out for with k and substring lengths?

Ensure s.length is divisible by k, and handle exact substring boundaries to avoid off-by-one errors.

Is sorting substrings enough to verify rearrangement?

No, sorting alone does not account for multiple identical substrings; frequency maps are required.

How does the Hash Table plus String pattern apply here?

It tracks how many times each substring occurs and ensures t can be built using these counts without unnecessary permutations.

terminal

Solution

Solution 1: Hash Table

Let the length of the string $s$ be $n$, then the length of each substring is $m = n / k$.

1

2

3

4

5

6

7

8

9

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())

Continue Practicing

#3458 select k disjoint special substrings #3545 minimum deletions for at most k distinct characters #3556 sum of largest prime substrings