Problem Description

You are given two strings s and t that are anagrams of each other (they contain the same characters with the same frequencies). You are also given an integer k.

Your task is to determine if you can:

1. Split string s into exactly k equal-sized substrings
2. Rearrange these substrings in any order
3. Concatenate them to form string t

The key points to understand:

• Both strings must have a length divisible by k (since we need equal-sized substrings)
• Each substring will have length n/k where n is the length of the strings
• The substrings are contiguous sequences from the original string s
• You can only rearrange the order of the substrings, not the characters within each substring

For example, if s = "abcd", t = "cdab", and k = 2:

• Split s into 2 equal parts: ["ab", "cd"]
• Rearrange to ["cd", "ab"]
• Concatenate to get "cdab" which equals t
• Return true

The solution uses a hash table to count occurrences of each substring of length m = n/k in both strings. For string s, it increments the count, and for string t, it decrements the count. If all counts end up at zero, it means the same set of substrings appears in both strings, making the rearrangement possible.

Intuition

When we split string s into k equal parts and rearrange them to form t, we're essentially asking: do both strings contain the same collection of substrings of length m = n/k?

Think of it like having two boxes of puzzle pieces. If we cut string s into pieces, we get one set of puzzle pieces. If we cut string t into pieces the same way, we get another set. For the rearrangement to be possible, both boxes must contain exactly the same pieces (though possibly in different orders).

The key insight is that we don't actually need to try all possible rearrangements. We just need to verify that when both strings are cut into chunks of size m, they produce the same multiset of substrings.

Why does this work? Because if s can be rearranged to form t, then:

• The substrings we get from cutting s must be exactly the substrings that appear in t when cut the same way
• Each unique substring must appear the same number of times in both cuts

This leads us to a counting approach:

• For each substring of length m in s, we add 1 to its count
• For each substring of length m in t, we subtract 1 from its count
• If all counts end up at zero, it means every substring appears equally often in both strings

This is much more efficient than trying to generate and check all possible permutations of the k substrings, which would be k! possibilities.

Learn more about Sorting patterns.

Solution Approach

The solution uses a hash table to efficiently track and compare the substrings from both strings.

Implementation Steps:

1. Calculate substring length: First, we determine the length of each substring as m = n // k, where n is the length of the string. This ensures we split the string into k equal parts.

2. Initialize a counter: We use a Counter (hash table) called cnt to track the difference in occurrences of substrings between s and t.

3. Process both strings simultaneously: We iterate through both strings with a step size of m:

   for i in range(0, n, m):
       cnt[s[i : i + m]] += 1  # Add substring from s
       cnt[t[i : i + m]] -= 1  # Subtract substring from t

   • For each position i (0, m, 2m, ...), we extract a substring of length m
   • We increment the count for substrings from s
   • We decrement the count for substrings from t
   • This effectively computes the difference in substring occurrences

4. Verify the result: After processing all substrings, we check if all values in the counter are zero:

   return all(v == 0 for v in cnt.values())

   If all values are zero, it means:

   • Every substring that appears in s also appears in t
   • They appear with the same frequency
   • Therefore, we can rearrange the substrings from s to form t

Time Complexity: O(n) where n is the length of the strings, as we iterate through each string once and substring extraction is O(m) for each of the k substrings.

Space Complexity: O(k * m) for storing at most k different substrings of length m in the hash table.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Example: s = "abcdef", t = "cdefab", k = 3

Step 1: Calculate substring length

• String length n = 6
• Substring length m = n // k = 6 // 3 = 2
• So we'll split both strings into substrings of length 2

Step 2: Initialize counter

• Create an empty hash table cnt = {}

Step 3: Process both strings

We iterate with i = 0, 2, 4 (step size of m = 2):

When i = 0:

• Extract s[0:2] = "ab" → cnt["ab"] += 1 → cnt = {"ab": 1}
• Extract t[0:2] = "cd" → cnt["cd"] -= 1 → cnt = {"ab": 1, "cd": -1}

When i = 2:

• Extract s[2:4] = "cd" → cnt["cd"] += 1 → cnt = {"ab": 1, "cd": 0}
• Extract t[2:4] = "ef" → cnt["ef"] -= 1 → cnt = {"ab": 1, "cd": 0, "ef": -1}

When i = 4:

• Extract s[4:6] = "ef" → cnt["ef"] += 1 → cnt = {"ab": 1, "cd": 0, "ef": 0}
• Extract t[4:6] = "ab" → cnt["ab"] -= 1 → cnt = {"ab": 0, "cd": 0, "ef": 0}

Step 4: Verify result

• Check all values in cnt: all are 0 ✓
• Return true

This confirms that s split into ["ab", "cd", "ef"] can be rearranged to ["cd", "ef", "ab"] to form t = "cdefab".

The beauty of this approach is that we never explicitly tried different arrangements. We simply verified that both strings contain the same collection of substrings when cut into pieces of size 2.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. The algorithm iterates through both strings s and t once, creating substrings of length m = n/k. The loop runs k times (from 0 to n with step m), and each iteration performs substring extraction in O(m) time. Since we process all n characters total across all iterations (k * m = k * (n/k) = n), the overall time complexity is O(n).

The space complexity is O(n). The Counter dictionary cnt stores at most 2k unique substrings (up to k different substrings from s and k from t), where each substring has length m = n/k. In the worst case where all substrings are unique, the total space used is O(k * m) = O(k * n/k) = O(n). Additionally, the substring operations create temporary strings that contribute to the space complexity, resulting in O(n) total space.

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

Common Pitfalls

1. Not Validating Input Divisibility

The most critical pitfall is assuming that the string length is always divisible by k. If len(s) % k != 0, the division into equal-sized substrings becomes impossible, and the code might produce incorrect results or unexpected behavior.

Issue Example:

• If s = "abcde" (length 5) and k = 2, we get segment_length = 5 // 2 = 2
• The last segment extraction s[4:6] would only get "e" instead of a 2-character substring
• This leads to comparing unequal-length segments and incorrect results

Solution: Add validation at the beginning of the function:

def isPossibleToRearrange(self, s: str, t: str, k: int) -> bool:
    string_length = len(s)
  
    # Validate that the string can be evenly divided
    if string_length % k != 0:
        return False
  
    segment_length = string_length // k
    # ... rest of the code

2. Using String Slicing as Dictionary Keys Without Consideration

While Python handles string slices as immutable objects suitable for dictionary keys, in some languages or scenarios, developers might accidentally use mutable objects (like lists) for substring representation, which cannot be used as dictionary keys.

Issue Example: If someone modifies the code to work with character lists instead of strings:

# Wrong approach if working with lists
s_segment = list(s[start_index:start_index + segment_length])
segment_counter[s_segment] += 1  # TypeError: unhashable type: 'list'

Solution: Always ensure substring representations are immutable (strings, tuples) when using them as dictionary keys:

# If working with lists, convert to tuple or string
s_segment = tuple(s[start_index:start_index + segment_length])
# or
s_segment = ''.join(s[start_index:start_index + segment_length])

3. Incorrect Assumption About Empty Strings

The code doesn't handle edge cases where strings might be empty or k = 0.

Issue Example:

• If s = "", t = "", and k = 0, division by zero would occur
• If k = 0, the range iteration would be infinite

Solution: Add edge case handling:

def isPossibleToRearrange(self, s: str, t: str, k: int) -> bool:
    # Handle edge cases
    if k == 0:
        return False
    if len(s) == 0:
        return True  # Empty strings are considered equal
  
    string_length = len(s)
    if string_length % k != 0:
        return False
    # ... rest of the code