LeetCode Solutions Blog

Rearrange Characters to Make Target String

Number: 2372

Difficulty: Easy

Paid? No

Companies: Amazon

Problem Description

Given two 0-indexed strings s and target, determine the maximum number of copies of target that can be formed by rearranging characters taken from s. Each character from s can be used only once.

Key Insights

Count the frequency of each character in both s and target.
For each character in target, the number of copies possible is determined by the ratio of its count in s to its count in target.
The answer is the minimum of these ratios across all characters present in target since that represents the bottleneck.

Space and Time Complexity

Time Complexity: O(n + m), where n is the length of s and m is the length of target.
Space Complexity: O(1) because we only store frequency counts for a fixed set of lowercase English letters.

Solution

The approach uses frequency counting. First, we create a frequency map for s and another for target. For each character in target, we calculate how many full copies of that character can be taken from s by performing floor division of its count in s by its required count in target. The maximum number of copies of target that can be formed will be the minimum value from these calculations. This ensures that every character needed for target is available in sufficient quantity based on s.

Code Solutions

# Python solution to rearrange characters to form the target string
def rearrangeCharacters(s, target):
    # Create frequency counts for s and target
    freq_s = {}
    for char in s:
        freq_s[char] = freq_s.get(char, 0) + 1

    freq_target = {}
    for char in target:
        freq_target[char] = freq_target.get(char, 0) + 1

    # Initialize the maximum copies possible as a large number
    max_copies = float('inf')

    # For each unique character in target, determine how many copies can be formed
    for char in freq_target:
        # If a required character is missing in s, return 0 immediately
        if char not in freq_s:
            return 0
        # Determine the possible copies for current character
        copies_char = freq_s[char] // freq_target[char]
        # Update max_copies accordingly; the answer must satisfy all characters
        max_copies = min(max_copies, copies_char)

    return max_copies

# Example usage:
#print(rearrangeCharacters("ilovecodingonleetcode", "code"))  # Output: 2