Rearrange K Substrings to Form Target String — Solution
Rearrange K Substrings to Form Target String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Rearrange K Substrings to Form Target String is a medium coding problem on strings, hash table and sorting, asked in Amazon interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Sorting
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given two strings s and t that are anagrams of each other (they hold the same letters with the same counts), and an integer k that divides their common length.
Cut s into k contiguous pieces of equal length, put the pieces in any order you like, and glue them back together.
Return true if some order of the pieces produces exactly t, and false otherwise.
Example 1
Input: s = "abcd", t = "cdab", k = 2
Output: true
Explanation: The pieces are `ab` and `cd`; placing `cd` first gives `cdab`.
Example 2
Input: s = "aabbcc", t = "bbaacc", k = 3
Output: true
Explanation: Pieces `aa`, `bb`, `cc` reordered as `bb`, `aa`, `cc`.
Example 3
Input: s = "aabbcc", t = "bbaacc", k = 2
Output: false
Explanation: The pieces of `s` are `aab` and `bcc`, but `t` needs `bba` and `acc`.
Constraints
1 <= s.length == t.length <= 2 * 10^51 <= k <= s.lengths.length is divisible by ks and t consist only of lowercase English letterss and t are anagrams of each other
Hints for Rearrange K Substrings to Form Target String
Hint 1
Cut
tintokpieces of the same length too. Whatever order you choose for the pieces ofs, the result's pieces are exactly the pieces ofs.Hint 2
So the question becomes: are the two collections of pieces the same multiset?
Hint 3
Count the pieces of
sin a hash map, then subtract the pieces oft; every count must end at zero (or sort both lists and compare).
How to solve Rearrange K Substrings to Form Target String
Any arrangement of the pieces of s is a string whose k equal-length pieces are those same pieces in some order. So t is reachable exactly when cutting t the same way yields the same multiset of pieces.
Approach
- Let
m = n / k, the length of each piece. - For each
i = 0, m, 2m, …add one to the count ofs[i..i+m)in a hash map. - For each such
isubtract one from the count oft[i..i+m); if a count would go below zero, returnfalse. - Return
true— both sides hadkpieces, so no count is left positive.
Why it works
If t is a reordering of the pieces of s, then its j-th block of length m is one of those pieces, so the two multisets agree. Conversely, if the multisets agree, placing the pieces of s in the order the blocks of t appear reproduces t block by block.
Complexity
- Time —
O(n) expected (hashing each piece once) - Space —
O(n)
Pitfalls
- Being anagrams is not enough — the letters must stay grouped inside their pieces (the third example).
- With
k = 1there is one piece, so the answer is simply whethers == t. - Duplicate pieces are common; compare counts, not just sets.
Reference solution
Python
from collections import Counter
def isPossibleToRearrange(s: str, t: str, k: int) -> bool:
m = len(s) // k
pieces = Counter(s[i:i + m] for i in range(0, len(s), m))
for i in range(0, len(t), m):
piece = t[i:i + m]
if pieces[piece] == 0:
return False
pieces[piece] -= 1
return TrueJava
public static boolean isPossibleToRearrange(String s, String t, int k) {
int m = s.length() / k;
Map<String, Integer> count = new HashMap<>();
for (int i = 0; i < s.length(); i += m) count.merge(s.substring(i, i + m), 1, Integer::sum);
for (int i = 0; i < t.length(); i += m) {
String q = t.substring(i, i + m);
int c = count.getOrDefault(q, 0);
if (c == 0) return false;
count.put(q, c - 1);
}
return true;
}C++
bool isPossibleToRearrange(string s, string t, int k) {
int m = s.size() / k;
unordered_map<string, int> count;
for (int i = 0; i < (int)s.size(); i += m) count[s.substr(i, m)]++;
for (int i = 0; i < (int)t.size(); i += m) {
auto it = count.find(t.substr(i, m));
if (it == count.end() || it->second == 0) return false;
it->second--;
}
return true;
}JavaScript
var isPossibleToRearrange = function(s, t, k) {
var m = s.length / k;
var count = new Map();
for (var i = 0; i < s.length; i += m) {
var p = s.substring(i, i + m);
count.set(p, (count.get(p) || 0) + 1);
}
for (var j = 0; j < t.length; j += m) {
var q = t.substring(j, j + m);
var c = count.get(q) || 0;
if (c === 0) return false;
count.set(q, c - 1);
}
return true;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets