#2287

Easy

LeetCode Problem Workspace

Rearrange Characters to Make Target String

Calculate the maximum copies of a target string from letters in s using frequency counting and hash tables efficiently.

Problem Statement

Given two 0-indexed strings s and target, you can select letters from s and rearrange them to form new strings. Determine how many full copies of target can be constructed from letters in s.

Return the maximum number of times target can be formed by taking letters from s and rearranging them. Letters cannot be reused across multiple copies.

Examples

Example 1

Input: s = "ilovecodingonleetcode", target = "code"

Output: 2

For the first copy of "code", take the letters at indices 4, 5, 6, and 7. For the second copy of "code", take the letters at indices 17, 18, 19, and 20. The strings that are formed are "ecod" and "code" which can both be rearranged into "code". We can make at most two copies of "code", so we return 2.

Example 2

Input: s = "abcba", target = "abc"

Output: 1

We can make one copy of "abc" by taking the letters at indices 0, 1, and 2. We can make at most one copy of "abc", so we return 1. Note that while there is an extra 'a' and 'b' at indices 3 and 4, we cannot reuse the letter 'c' at index 2, so we cannot make a second copy of "abc".

Example 3

Input: s = "abbaccaddaeea", target = "aaaaa"

Output: 1

We can make one copy of "aaaaa" by taking the letters at indices 0, 3, 6, 9, and 12. We can make at most one copy of "aaaaa", so we return 1.

Constraints

1 <= s.length <= 100
1 <= target.length <= 10
s and target consist of lowercase English letters.

Solution Approach

Count Character Frequencies

Create hash tables for s and target to count the frequency of each letter. This allows precise tracking of available letters versus required letters.

Compute Maximum Copies

For each character in target, divide the count in s by the count needed for target. The minimum quotient across all characters determines the maximum number of target copies possible.

Return Result

Return the computed minimum as the answer. This ensures no letter is reused and the solution aligns with the Hash Table plus String pattern efficiently.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n + m) where n is the length of s and m is the length of target due to single pass frequency counting. Space complexity is O(1) in practice since there are at most 26 lowercase letters stored in hash tables.

What Interviewers Usually Probe

Asks if frequency counting is necessary for each character or can be optimized.
Wants confirmation that letters cannot be reused across target copies.
Checks understanding of hash table operations for string counting.

Common Pitfalls or Variants

Common pitfalls

Forgetting to take the minimum across all character counts in target.
Attempting to reuse letters from s for multiple target copies.
Not accounting for characters in target that do not exist in s.

Follow-up variants

Instead of lowercase letters, compute copies for uppercase or mixed-case target strings.
Determine maximum copies when s can contain non-alphabetic characters that should be ignored.
Compute copies when target has repeating letters with different frequencies.

FAQ

What is the easiest way to solve Rearrange Characters to Make Target String?

Use hash tables to count letters in s and target, then divide available counts by required counts to find the maximum copies.

Can letters in s be reused across multiple copies of target?

No, each letter from s can only be used once per copy of target, which is why we take the minimum across character ratios.

How does this problem relate to Hash Table plus String pattern?

The solution relies on counting character frequencies in both strings efficiently using hash tables and simple arithmetic to compute maximum copies.

What if target contains letters not present in s?

If any letter in target is missing from s, the maximum number of copies is zero.

What is the time complexity for this approach?

It is O(n + m), where n is the length of s and m is the length of target, because each string is scanned once for counting.

terminal

Solution

Solution 1: Counting

We count the occurrences of each character in the strings $\textit{s}$ and $\textit{target}$, denoted as $\textit{cnt1}$ and $\textit{cnt2}$. For each character in $\textit{target}$, we calculate the number of times it appears in $\textit{cnt1}$ divided by the number of times it appears in $\textit{cnt2}$, and take the minimum value.

1

2

3

4

5

class Solution:
    def rearrangeCharacters(self, s: str, target: str) -> int:
        cnt1 = Counter(s)
        cnt2 = Counter(target)
        return min(cnt1[c] // v for c, v in cnt2.items())

Continue Practicing

#2284 sender with largest word count #2283 check if number has equal digit count and digit value #2351 first letter to appear twice