LeetCode 2287 - Rearrange Characters to Make Target String

LeetCode Problem 2287

Difficulty: 🟢 Easy
Topics: Hash Table, String, Counting

Solution

Problem Understanding

The problem gives us two strings, s and target. We are allowed to take characters from s and rearrange them in any order to form copies of target.

Each character in s can only be used once. The goal is to determine the maximum number of complete copies of target that can be constructed using the available characters in s.

The important detail is that order does not matter. We are not searching for substrings or subsequences. We only care about how many times each character appears. For example, if target = "code", then every copy requires:

• one 'c'
• one 'o'
• one 'd'
• one 'e'

If s contains two copies of each required character, then we can build exactly two copies of "code".

The constraints are very small:

• s.length <= 100
• target.length <= 10

This immediately suggests that counting frequencies is sufficient. We do not need advanced algorithms or optimizations for large inputs.

A few important edge cases stand out immediately:

• target may contain repeated characters, such as "aaaaa". In that case, we must ensure we divide by the required count correctly.
• s may not contain a required character at all, which means the answer is 0.
• s may contain many extra irrelevant characters that do not help build additional copies.
• The answer is limited by the "most scarce" required character.

For example:

• If target = "aab"
• and s contains 5 'a' characters and 2 'b' characters

then:

• 'a' allows 5 // 2 = 2 copies
• 'b' allows 2 // 1 = 2 copies

So the final answer is 2.

Approaches

Brute Force Approach

A brute force solution would repeatedly try to construct one copy of target at a time.

We could:

1. Count all characters in s
2. Attempt to subtract the characters needed for one copy of target
3. If all required characters are available, increment the answer
4. Repeat until construction is impossible

This approach is correct because every successful iteration consumes exactly the characters needed for one copy of target.

However, this method repeatedly scans and updates the counts. While the constraints are small enough that it would still pass, it is unnecessarily repetitive.

The core inefficiency is that we already know the limiting factor is the least available required character. Repeated simulation is not needed.

Optimal Approach

The key observation is that each character independently limits how many copies of target can be formed.

Suppose:

• target requires k copies of character c
• s contains n copies of character c

Then character c alone allows at most:

$$\left\lfloor \frac{n}{k} \right\rfloor$$

copies of target.

Since every required character must be available simultaneously, the answer is simply the minimum value across all required characters.

This transforms the problem into a frequency counting problem.

We:

1. Count character frequencies in s
2. Count character frequencies in target
3. For every character in target, compute:

• available // required

4. Return the minimum result

This is efficient, simple, and mathematically direct.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(	s	+ answer ×
Optimal	O(	s	+

Algorithm Walkthrough

1. Create a frequency map for string s.

We count how many times each character appears in s. This tells us the total supply of each letter available for constructing copies of target. 2. Create a frequency map for string target.

This tells us how many copies of each character are required for one complete target string. 3. Initialize the answer as a very large number.

We will minimize this value across all required characters. 4. Iterate through every character required by target.

For each character:

• Let available be the count from s
• Let required be the count from target

Compute:

$$\text{copies} = \frac{\text{available}}{\text{required}}$$

using integer division. 5. Update the answer with the minimum value.

The smallest ratio determines the total number of complete copies that can be formed. 6. Return the final answer.

Why it works

Every copy of target requires a fixed number of each character. A character can only contribute as many complete copies as its available frequency allows.

For each required character:

$$\left\lfloor \frac{\text{available}}{\text{required}} \right\rfloor$$

gives the maximum copies supported by that character alone.

Since every character requirement must be satisfied simultaneously, the true answer is the minimum across all required characters. This guarantees correctness.

Python Solution

from collections import Counter

class Solution:
    def rearrangeCharacters(self, s: str, target: str) -> int:
        source_count = Counter(s)
        target_count = Counter(target)

        max_copies = float("inf")

        for char, required in target_count.items():
            available = source_count[char]
            max_copies = min(max_copies, available // required)

        return max_copies

The implementation uses Python's Counter from the collections module to simplify frequency counting.

First, source_count stores how many times each character appears in s.

Next, target_count stores how many times each character is needed for one copy of target.

The variable max_copies starts at infinity because we are searching for the minimum limiting ratio.

The loop iterates through every required character in target. For each one, we compute how many copies are possible using integer division:

available // required

We continuously minimize max_copies because the scarcest required character determines the answer.

Finally, the method returns the computed minimum.

Go Solution

func rearrangeCharacters(s string, target string) int {
	sourceCount := make([]int, 26)
	targetCount := make([]int, 26)

	for _, ch := range s {
		sourceCount[ch-'a']++
	}

	for _, ch := range target {
		targetCount[ch-'a']++
	}

	answer := int(^uint(0) >> 1)

	for i := 0; i < 26; i++ {
		if targetCount[i] > 0 {
			copies := sourceCount[i] / targetCount[i]

			if copies < answer {
				answer = copies
			}
		}
	}

	return answer
}

The Go solution uses fixed-size integer arrays of length 26 because the problem guarantees lowercase English letters only.

Instead of hash maps, arrays provide direct indexing with:

ch - 'a'

The expression:

int(^uint(0) >> 1)

initializes answer to the maximum possible integer value in Go.

The rest of the logic matches the Python implementation exactly. We compute the limiting ratio for every required character and return the minimum.

Worked Examples

Example 1

Input:

s = "ilovecodingonleetcode"
target = "code"

Step 1: Count characters in target

Character	Required
c	1
o	1
d	1
e	1

Step 2: Count characters in s

Relevant counts:

Character	Available
c	2
o	3
d	2
e	4

Step 3: Compute possible copies

Character	Available	Required	Copies Possible
c	2	1	2
o	3	1	3
d	2	1	2
e	4	1	4

Minimum value:

min(2, 3, 2, 4) = 2

Answer:

2

Example 2

Input:

s = "abcba"
target = "abc"

Target counts

Character	Required
a	1
b	1
c	1

Source counts

Character	Available
a	2
b	2
c	1

Copies possible

Character	Available	Required	Copies Possible
a	2	1	2
b	2	1	2
c	1	1	1

Minimum:

1

Answer:

1

Example 3

Input:

s = "abbaccaddaeea"
target = "aaaaa"

Target counts

Character	Required
a	5

Source counts

Character	Available
a	5

Copies possible

Character	Available	Required	Copies Possible
a	5	5	1

Answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(	s
Space	O(1)	At most 26 lowercase English letters are stored

The algorithm performs a single pass over s and target to compute character frequencies. The final loop iterates over at most 26 characters.

Although hash maps or counters are used conceptually, the alphabet size is fixed to lowercase English letters, so the space usage is constant.

Test Cases

from collections import Counter

class Solution:
    def rearrangeCharacters(self, s: str, target: str) -> int:
        source_count = Counter(s)
        target_count = Counter(target)

        answer = float("inf")

        for char, required in target_count.items():
            answer = min(answer, source_count[char] // required)

        return answer

sol = Solution()

assert sol.rearrangeCharacters("ilovecodingonleetcode", "code") == 2
# basic example with multiple copies

assert sol.rearrangeCharacters("abcba", "abc") == 1
# only one full copy possible

assert sol.rearrangeCharacters("abbaccaddaeea", "aaaaa") == 1
# repeated character requirement

assert sol.rearrangeCharacters("aaaaaa", "aa") == 3
# exact repeated grouping

assert sol.rearrangeCharacters("abc", "d") == 0
# missing required character

assert sol.rearrangeCharacters("zzz", "zzzz") == 0
# insufficient frequency

assert sol.rearrangeCharacters("a", "a") == 1
# minimum valid input

assert sol.rearrangeCharacters("bbbbbb", "bb") == 3
# repeated single character target

assert sol.rearrangeCharacters("abcabcabc", "abc") == 3
# multiple exact copies

assert sol.rearrangeCharacters("aabbbcccc", "abc") == 1
# limited by smallest count

assert sol.rearrangeCharacters("aaaaaaaaaa", "aaa") == 3
# integer division truncation

Test Case Summary

Test	Why
"ilovecodingonleetcode", "code"	Standard example with multiple copies
"abcba", "abc"	Limited by one character
"abbaccaddaeea", "aaaaa"	Repeated character requirement
"aaaaaa", "aa"	Exact repeated grouping
"abc", "d"	Missing character case
"zzz", "zzzz"	Insufficient frequency
"a", "a"	Smallest valid input
"bbbbbb", "bb"	Single repeated character target
"abcabcabc", "abc"	Multiple exact copies
"aabbbcccc", "abc"	Limited by minimum ratio
"aaaaaaaaaa", "aaa"	Tests floor division behavior

Edge Cases

Target Contains Repeated Characters

A common mistake is treating every character independently without considering how many times it appears in target.

For example:

s = "aaaaaa"
target = "aaa"

Even though there are six 'a' characters, each copy requires three of them. The correct answer is:

6 // 3 = 2

The implementation handles this correctly by dividing available frequency by required frequency.

Missing Required Character

If s does not contain a character required by target, the answer must immediately become 0.

Example:

s = "abc"
target = "abcd"

The character 'd' appears zero times in s, so:

0 // 1 = 0

Since we take the minimum across all required characters, the algorithm correctly returns 0.

Extra Irrelevant Characters

S may contain many characters that are not useful for constructing target.

Example:

s = "xyzxyzxyzabc"
target = "abc"

The extra 'x', 'y', and 'z' characters should not affect the result.

The implementation naturally ignores irrelevant characters because it only iterates through characters required by target.