LeetCode 3365 - Rearrange K Substrings to Form Target String

This problem asks whether it is possible to rearrange k contiguous equal-length substrings of a string s to form another string t, given that s and t are anagrams.

leetcodemediumhash-tablestringsorting

LeetCode Problem 3365

Difficulty: 🟡 Medium
Topics: Hash Table, String, Sorting

Solution

Problem Understanding

This problem asks whether it is possible to rearrange k contiguous equal-length substrings of a string s to form another string t, given that s and t are anagrams. In simpler terms, we are splitting s into k pieces of the same size, then permuting these pieces in any order to see if we can produce t. The input consists of two strings s and t, and an integer k. The output is a boolean indicating whether the rearrangement is possible.

The constraints are crucial: s and t have lengths up to 2 * 10^5, and s.length is divisible by k, so each substring has length n = len(s) / k. The fact that s and t are guaranteed to be anagrams ensures that the characters themselves are compatible; the only challenge is arranging substrings of the correct size. Edge cases include k = 1 (entire string is one substring, so only exact match works) and k = len(s) (each character is a substring, so any permutation works).

Approaches

The brute-force approach is to generate all permutations of the k substrings of s and check if any concatenation equals t. While this guarantees correctness, it is infeasible for large strings, as there are k! permutations, and each concatenation check costs O(n) time. For k around 10^5, this is astronomically slow.

The optimal approach relies on the insight that we do not need to check all permutations explicitly. Since substrings are of equal length, the problem reduces to checking whether the multiset of substrings from s matches the multiset of substrings from t. By breaking both s and t into k equal-length chunks and counting how many times each substring occurs, we can compare the counts. If they match, a rearrangement exists; otherwise, it does not. We can efficiently implement this using a hash map (dictionary in Python, map in Go).

Approach Time Complexity Space Complexity Notes
Brute Force O(k! * n) O(k) Generate all permutations of substrings and check concatenation
Optimal O(n) O(n) Use hash map to count frequency of substrings and compare

Algorithm Walkthrough

  1. Compute the length of each substring as sub_len = len(s) // k.
  2. Initialize a hash map to count the frequency of each substring of length sub_len in s.
  3. Iterate over s in steps of sub_len, extract each substring, and increment its count in the hash map.
  4. Repeat the same process for t, decrementing counts in the hash map for each substring.
  5. After processing both strings, check the hash map. If all counts are zero, it means s and t contain the same substrings with the same frequencies, so return true. Otherwise, return false.

Why it works: The hash map comparison ensures that the multiset of substrings in s matches that in t. Since the order of substrings can be rearranged arbitrarily, having the same multiset guarantees that a valid rearrangement exists.

Python Solution

class Solution:
    def isPossibleToRearrange(self, s: str, t: str, k: int) -> bool:
        n = len(s)
        sub_len = n // k
        count = {}

        for i in range(0, n, sub_len):
            sub_s = s[i:i+sub_len]
            count[sub_s] = count.get(sub_s, 0) + 1

        for i in range(0, n, sub_len):
            sub_t = t[i:i+sub_len]
            if sub_t not in count:
                return False
            count[sub_t] -= 1
            if count[sub_t] == 0:
                del count[sub_t]

        return not count

In the Python code, we first calculate the length of each substring. We then iterate over s and store the frequency of each substring in a dictionary. Next, we iterate over t, decrementing the counts, and immediately return false if a substring is missing. If all counts reach zero, we return true.

Go Solution

func isPossibleToRearrange(s string, t string, k int) bool {
    n := len(s)
    subLen := n / k
    count := make(map[string]int)

    for i := 0; i < n; i += subLen {
        subS := s[i:i+subLen]
        count[subS]++
    }

    for i := 0; i < n; i += subLen {
        subT := t[i:i+subLen]
        if count[subT] == 0 {
            return false
        }
        count[subT]--
        if count[subT] == 0 {
            delete(count, subT)
        }
    }

    return len(count) == 0
}

In Go, we use a map to count substrings. The logic mirrors the Python solution, with attention to Go syntax and the use of delete to remove entries from the map once the count reaches zero.

Worked Examples

Example 1: s = "abcd", t = "cdab", k = 2

Substring length = 2

Substrings of s: ["ab", "cd"] → count = {"ab":1, "cd":1}

Substrings of t: ["cd", "ab"] → decrement: "cd"→0, "ab"→0 → map empty → return True

Example 2: s = "aabbcc", t = "bbaacc", k = 3

Substring length = 2

Substrings of s: ["aa", "bb", "cc"] → count = {"aa":1, "bb":1, "cc":1}

Substrings of t: ["bb", "aa", "cc"] → decrement: "bb"→0, "aa"→0, "cc"→0 → map empty → return True

Example 3: s = "aabbcc", t = "bbaacc", k = 2

Substring length = 3

Substrings of s: ["aab", "bcc"] → count = {"aab":1, "bcc":1}

Substrings of t: ["bba", "acc"] → "bba" not in map → return False

Complexity Analysis

Measure Complexity Explanation
Time O(n) We iterate over both s and t once in steps of sub_len, processing each character exactly twice
Space O(n) We store counts for up to k substrings, each of length n/k, so total space is O(n)

The linear time complexity ensures the solution is efficient even for the maximum input size of 2 * 10^5. The hash map guarantees constant-time insertions and lookups on average.

Test Cases

# Provided examples
assert Solution().isPossibleToRearrange("abcd", "cdab", 2) == True  # basic reorder
assert Solution().isPossibleToRearrange("aabbcc", "bbaacc", 3) == True  # multiple substrings
assert Solution().isPossibleToRearrange("aabbcc", "bbaacc", 2) == False  # mismatch in substring grouping

# Edge cases
assert Solution().isPossibleToRearrange("abc", "abc", 1) == True  # entire string as one substring
assert Solution().isPossibleToRearrange("abc", "cba", 3) == True  # each char is a substring
assert Solution().isPossibleToRearrange("aabb", "abab", 2) == True  # repeated letters, split works
assert Solution().isPossibleToRearrange("aaaa", "aaaa", 2) == True  # identical substrings

# Large input
s = "ab" * 100000
t = "ba" * 100000
assert Solution().isPossibleToRearrange(s, t, 200000) == True  # stress test large input
Test Why
"abcd", "cdab", 2 Valid rearrangement of 2 substrings
"aabbcc", "bbaacc", 3 Valid rearrangement of 3 substrings
"aabbcc", "bbaacc", 2 Substring lengths do not match t
"abc", "abc", 1 Entire string as a single substring
"abc", "cba", 3 Each character is a substring, full permutation allowed
"aabb", "abab", 2 Substrings with repeated letters, still works
"aaaa", "aaaa", 2 Identical substrings, edge case
Large repeated string Stress test for performance

Edge Cases

One important edge case is when k = 1. Here, the entire string is a single substring, so s must exactly equal t. The implementation handles this