Rearrange K Substrings to Form Target String

Medium
1821.

Rearrange K Substrings to Form Target String

Rearrange K Substrings to Form Target String is a medium coding problem on strings, hash table and sorting, asked in Amazon interviews.

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^5
  • 1 <= k <= s.length
  • s.length is divisible by k
  • s and t consist only of lowercase English letters
  • s and t are anagrams of each other
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {string} t
 * @param {number} k
 * @return {boolean}
 */
var isPossibleToRearrange = function(s, t, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • 1 <= k <= s.length
  • s.length is divisible by k
  • s and t consist only of lowercase English letters
  • s and t are anagrams of each other

Hints for Rearrange K Substrings to Form Target String

  1. Hint 1

    Cut t into k pieces of the same length too. Whatever order you choose for the pieces of s, the result's pieces are exactly the pieces of s.

  2. Hint 2

    So the question becomes: are the two collections of pieces the same multiset?

  3. Hint 3

    Count the pieces of s in a hash map, then subtract the pieces of t; 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

  1. Let m = n / k, the length of each piece.
  2. For each i = 0, m, 2m, … add one to the count of s[i..i+m) in a hash map.
  3. For each such i subtract one from the count of t[i..i+m); if a count would go below zero, return false.
  4. Return true — both sides had k pieces, 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 = 1 there is one piece, so the answer is simply whether s == 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 True

Java

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