Skip to main content
Talentd

Rearrange K Substrings to Form Target String - Solution & Explanation

MediumHash TableStringSorting14 min read
Practice this problem

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

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.

Approach 1: Check Permutation of Substrings

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

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(1) because we only check simple arithmetic.

Space Complexity: O(1) since no additional space is used.

Try this approach in the editor →

Approach 2: Validate Character Distribution

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

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(1), since checking divisibility is constant time.

Space Complexity: O(1), no extra allocation.

Try this approach in the editor →

Approach 3: Hash Table

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Check Permutation of SubstringsO(n log k)O(k * m)Simple implementation when substring comparison or sorting is acceptable
Validate Character Distribution with SignaturesO(n)O(k)Optimal approach when minimizing sorting overhead and using hash maps

Video Solution

3365. Rearrange K Substrings to Form Target String | HashMap • Aryan Mittal • 679 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Rearrange K Substrings to Form Target String easy or hard?
Rearrange K Substrings to Form Target String is generally considered a medium-level problem. The difficulty comes from recognizing that the strings must be partitioned into equal blocks and treated as a multiset comparison rather than character-by-character matching.
Rearrange K Substrings to Form Target String Python/Java solution
Most implementations split the string using substring operations, then track counts using a dictionary in Python or a HashMap in Java. Either compare sorted substring lists or maintain a frequency map of substring signatures. Both approaches work across languages like Python, Java, C++, and JavaScript.
How to solve Rearrange K Substrings to Form Target String in O(n)?
Split both strings into k blocks of length n/k and compute a character frequency signature for each block. Store signatures from the first string in a hash map and subtract counts while scanning the target string. If every signature count returns to zero, the rearrangement is valid. Each character is processed once, giving linear time.
What is the best approach for Rearrange K Substrings to Form Target String?
The most efficient approach splits both strings into k equal-length substrings and compares them using a hash map of substring signatures. Each substring contributes a frequency key, and matching counts confirm whether rearrangement is possible. This method runs in O(n) time and O(k) space and avoids sorting overhead.
Is Rearrange K Substrings to Form Target String asked at Google/Amazon/Meta?
Problems involving substring partitioning, hash maps, and string rearrangement are common in interviews at companies like Amazon, Google, and Meta. Variants often test the ability to compare groups of substrings efficiently using hashing or frequency arrays.
What data structure is used in Rearrange K Substrings to Form Target String?
The core data structure is a hash table that stores substring frequencies or signature counts. Arrays are also used to build character frequency vectors for each substring. Sorting can be used as an alternative when comparing substring lists directly.
What is the time complexity of Rearrange K Substrings to Form Target String?
The optimal solution runs in O(n) time because each character is processed once while building substring signatures. A simpler solution that sorts the k substrings requires O(n log k) time due to the sorting step. Space complexity is typically O(k) to store substring counts or signatures.

Ready to solve this problem?

Practice Rearrange K Substrings to Form Target String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters