Scale Engineer

Rearrange K Substrings to Form Target String

Med
#2990Time: `O(n * log(k))`, where `n` is the length of the strings and `k` is the number of substrings. Generating the substrings takes `O(n)`. Sorting a list of `k` strings, where each string comparison takes `O(n/k)`, results in a total sorting time of `O(k * log(k) * (n/k)) = O(n * log(k))`.Space: `O(n)`. We need two lists to store the substrings. Each list contains `k` substrings of length `n/k`, so the total space required is `2 * k * (n/k) = O(n)`.
Algorithms
Sorting
Data structures
Hash TableString

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach tackles the problem by treating the substrings from s and t as two multisets. The core idea is that if two multisets are identical, their sorted versions will also be identical. We generate the substrings for both s and t, sort them, and then perform a direct comparison.

Algorithm

    1. Calculate the substring length subLen = s.length() / k.
    1. Create an empty list s_substrings.
    1. Split s into k substrings of length subLen and add them to s_substrings.
    1. Create an empty list t_substrings.
    1. Split t into k substrings of length subLen and add them to t_substrings.
    1. Sort the s_substrings list.
    1. Sort the t_substrings list.
    1. Return true if the sorted lists are identical, otherwise return false.

Walkthrough

The problem asks if the multiset of k substrings from s can be rearranged to form t. This is equivalent to checking if the multiset of substrings from s is identical to the multiset of substrings from t. A straightforward way to compare two multisets is to convert them to sorted lists and check for equality. The algorithm proceeds as follows:

  1. Calculate the length of each of the k substrings: subLen = s.length() / k.
  2. Create two lists, s_subs and t_subs.
  3. Iterate through s and t with a step size of subLen, extracting each substring and adding it to the respective list.
  4. Sort both s_subs and t_subs lexicographically.
  5. Finally, compare the two sorted lists. If they are equal, it means s and t are composed of the same substrings, and we return true. Otherwise, we return false.
import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution {    public boolean canRearrange(String s, String t, int k) {        int n = s.length();        // The problem guarantees s.length() is divisible by k.        int subLen = n / k;         List<String> s_subs = new ArrayList<>(k);        for (int i = 0; i < n; i += subLen) {            s_subs.add(s.substring(i, i + subLen));        }         List<String> t_subs = new ArrayList<>(k);        for (int i = 0; i < n; i += subLen) {            t_subs.add(t.substring(i, i + subLen));        }         Collections.sort(s_subs);        Collections.sort(t_subs);         return s_subs.equals(t_subs);    }}

Complexity

Time

`O(n * log(k))`, where `n` is the length of the strings and `k` is the number of substrings. Generating the substrings takes `O(n)`. Sorting a list of `k` strings, where each string comparison takes `O(n/k)`, results in a total sorting time of `O(k * log(k) * (n/k)) = O(n * log(k))`.

Space

`O(n)`. We need two lists to store the substrings. Each list contains `k` substrings of length `n/k`, so the total space required is `2 * k * (n/k) = O(n)`.

Trade-offs

Pros

  • Conceptually simple and relies on standard sorting and comparison logic.

  • Easy to implement using built-in list and sorting functionalities.

Cons

  • The time complexity is dominated by sorting, making it less efficient than a hash-based approach.

  • Requires storing all substrings for both s and t in memory, leading to O(n) space usage.

Solutions

class Solution {public  boolean isPossibleToRearrange(String s, String t, int k) {    Map<String, Integer> cnt = new HashMap<>(k);    int n = s.length();    int m = n / k;    for (int i = 0; i < n; i += m) {      cnt.merge(s.substring(i, i + m), 1, Integer : : sum);      cnt.merge(t.substring(i, i + m), -1, Integer : : sum);    }    for (int v : cnt.values()) {      if (v != 0) {        return false;      }    }    return true;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem