We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Rearrange K Substrings to Form Target String

Difficulty: Medium

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.

Key Insights

  • Both strings s and t are anagrams, which means they contain the same characters with the same frequency.
  • The length of s must be divisible by k to allow for equal-sized substrings.
  • Each substring will have a length of length(s) / k.
  • The character distribution in the substrings after rearrangement must match that of string t.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s (or t). Space Complexity: O(1), since we are only using a fixed-size frequency array for lowercase English letters.

Solution

To solve this problem, we can use the following approach:

  1. Check if the length of s is divisible by k.
  2. Calculate the length of each substring as length(s) / k.
  3. Count the frequency of each character in string s.
  4. For each character, determine how many full substrings can be formed using the character's frequency.
  5. Ensure that these substrings can be rearranged to match the character frequencies needed to form string t.
  6. If all conditions are met, return true; otherwise, return false.

We will use a frequency array to count the characters, which allows us to efficiently manage and compare the required counts.

Code Solutions

def can_form_target_string(s, t, k):
    if len(s) % k != 0:
        return False
    
    substring_length = len(s) // k
    freq = [0] * 26  # For 26 lowercase English letters
    
    # Count frequency of characters in s
    for char in s:
        freq[ord(char) - ord('a')] += 1
    
    # Check if we can form k substrings
    for count in freq:
        if count % k != 0:
            return False
    
    return True
← Back to All Questions