3365. Rearrange K Substrings to Form Target String

MediumHash TableStringSorting

Problem Description

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.

Intuition

The problem asks us to determine if we can rearrange k equal-sized substrings of s to form t. Since s and t are anagrams, they contain the same characters in the same frequencies, so the primary challenge is to manage the rearrangement of substrings.

To solve this, calculate the length of each substring, m, which is n / k, where n is the length of s. For both strings s and t, extract substrings of length m. Use a hash table or counter to keep track of how many times each substring appears in s and t.

By iterating through the string s, increment the count for substrings in s and decrement it for substrings in t. At the end, if all the counts are zero, it means that we can rearrange the k substrings of s to form t. Thus, we return true; otherwise, return false.

Learn more about Sorting patterns.

Solution Approach

The solution employs a hash table to manage and compare the frequency of equal-sized substrings in both s and t. Here's a step-by-step breakdown of the implementation:

Calculate Substring Length: Determine the length m of each substring which should be n / k where n is the total length of the string s.
Initialize Counter: Use a hash table or counter, cnt, to track the frequency of each substring from both s and t.
Count Substrings in s and t:
- Iterate through the string s with a step size of m. For each position i, extract a substring of length m.
- Increment the count for this substring in cnt when it appears in s.
- Decrement the count for the corresponding substring extracted from t to ensure that the substrings of s can be rearranged to create t.
Validation: After processing all substrings, check if all counts in the counter cnt are zero. This tells us that each substring in s can be rearranged completely to form t.
Return Result: If the condition holds (all counts zero), return true; otherwise, return false.

The solution effectively leverages a hash table to balance the quick lookup and update of substring frequencies, ensuring that the rearrangement potential is checked efficiently.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take a small example with strings s = "abcabc" and t = "bcaacb", and k = 2.

Calculate Substring Length:

Given the length of s is 6 and k = 2, the length m of each substring should be n / k = 6 / 2 = 3.
Initialize Counter:

We will use a counter cnt to keep track of the frequency of each substring of length m.
Count Substrings in s and t:
- For s:
  - We extract s[0:3] = "abc" and s[3:6] = "abc".
  - Increment the counts in cnt, resulting in cnt = {"abc": 2}.
- For t:
  - We extract t[0:3] = "bca" and t[3:6] = "acb".
  - Decrement the counts in cnt, leading to cnt = {"abc": 2, "bca": -1, "acb": -1}.
Validation:

Check whether all the counts in the counter cnt are zero. Currently, cnt has non-zero counts, indicating that the substrings cannot be rearranged to match t.
Return Result:

Since not all counts are zero, return false.

Thus, in this example, it's not possible to rearrange the k equal-sized substrings of s to form t. The function would return false.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def isPossibleToRearrange(self, s: str, t: str, k: int) -> bool:
5        # Initialize a counter to keep track of substring frequencies
6        cnt = Counter()
7      
8        # Get the length of the string s
9        n = len(s)
10      
11        # Calculate the length of each segment by dividing n by k
12        m = n // k
13      
14        # Iterate over the string with a step size of m
15        for i in range(0, n, m):
16            # Increment the count for the substring from s
17            cnt[s[i: i + m]] += 1
18            # Decrement the count for the corresponding substring from t
19            cnt[t[i: i + m]] -= 1
20      
21        # Check if all the values in the counter are zero, indicating a valid rearrangement
22        return all(value == 0 for value in cnt.values())
23

1import java.util.HashMap;
2import java.util.Map;
3
4class Solution {
5    public boolean isPossibleToRearrange(String s, String t, int k) {
6        // Create a map to count substrings of length m in both strings, s and t.
7        Map<String, Integer> countMap = new HashMap<>(k);
8
9        // Get the total length of string s.
10        int n = s.length();
11      
12        // Calculate the size of each segment.
13        int segmentLength = n / k;
14      
15        // Iterate over the strings in increments of segmentLength.
16        for (int i = 0; i < n; i += segmentLength) {
17            // Extract the substring of size segmentLength from s and increase its count.
18            countMap.merge(s.substring(i, i + segmentLength), 1, Integer::sum);
19          
20            // Extract the substring of size segmentLength from t and decrease its count.
21            countMap.merge(t.substring(i, i + segmentLength), -1, Integer::sum);
22        }
23      
24        // Check if all values in the map are zero.
25        for (int count : countMap.values()) {
26            // If any count is not zero, s cannot be rearranged to match t in segments.
27            if (count != 0) {
28                return false;
29            }
30        }
31      
32        // If all counts are zero, then s can be rearranged to match t.
33        return true;
34    }
35}
36

1#include <unordered_map>
2#include <string>
3
4class Solution {
5public:
6    // Function to check if it's possible to rearrange string s to form string t in chunks of size k
7    bool isPossibleToRearrange(std::string s, std::string t, int k) {
8        // `chunkCount` keeps track of occurrences of each chunk in s and t
9        std::unordered_map<std::string, int> chunkCount;
10      
11        int n = s.size();  // Length of the strings
12        int chunkSize = n / k;  // Determine the size of each chunk based on k
13      
14        // Iterate over the strings in increments of `chunkSize`
15        for (int i = 0; i < n; i += chunkSize) {
16            // Increment count for the chunk from s
17            chunkCount[s.substr(i, chunkSize)]++;
18            // Decrement count for the chunk from t
19            chunkCount[t.substr(i, chunkSize)]--;
20        }
21      
22        // Check if any chunk has a non-zero count, indicating an imbalance
23        for (const auto& [chunk, count] : chunkCount) {
24            if (count != 0) {
25                return false;  // If the count is not zero, return false
26            }
27        }
28      
29        return true;  // All chunks are balanced, return true
30    }
31};
32

1function isPossibleToRearrange(s: string, t: string, k: number): boolean {
2    // Record to store the frequency difference of substrings between s and t
3    const substringFrequency: Record<string, number> = {};
4  
5    // Length of the string s
6    const n = s.length;
7  
8    // Length of each substring (m should be the size of each group)
9    const substringLength = Math.floor(n / k);
10
11    // Iterate through the string s and t in steps of m (substringLength)
12    for (let i = 0; i < n; i += substringLength) {
13        // Get the substring from s and increase its count in the map
14        const substringS = s.slice(i, i + substringLength);
15        substringFrequency[substringS] = (substringFrequency[substringS] || 0) + 1;
16      
17        // Get the substring from t and decrease its count in the map
18        const substringT = t.slice(i, i + substringLength);
19        substringFrequency[substringT] = (substringFrequency[substringT] || 0) - 1;
20    }
21  
22    // Check if all frequency differences are zero
23    return Object.values(substringFrequency).every(count => count === 0);
24}
25

Time and Space Complexity

The time complexity is O(n) since the code processes each character of the strings s and t exactly once and updates the Counter dictionary, which is considered a constant time operation given the character set is finite.

The space complexity is also O(n) because the Counter dictionary stores at most n keys when each substring partition of the characters from s and t are unique, thereby using space proportional to the length of s.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: