Rearrange Characters to Make Target String - Solution & Explanation
Problem Statement
You are given two 0-indexed strings s and target. You can take some letters from s and rearrange them to form new strings.
Return the maximum number of copies of target that can be formed by taking letters from s and rearranging them.
Example 1:
Input: s = "ilovecodingonleetcode", target = "code" Output: 2 Explanation: 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 Explanation: 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 Explanation: 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 <= 1001 <= target.length <= 10sandtargetconsist of lowercase English letters.
Note: This question is the same as 1189: Maximum Number of Balloons.
Approach Overview
Problem Overview: You receive two strings: s and target. Characters from s can be rearranged and used at most once. The task is to determine how many complete copies of target you can build using those characters.
The core idea is counting how many times each character appears in both strings. Each copy of target requires a fixed number of each character. The maximum number of copies you can form is limited by the scarcest required character.
Approach 1: Frequency Count Method (O(n + m) time, O(k) space)
This approach uses a hash map (dictionary) to store character frequencies. First iterate through s and record how many times each character appears. Then count frequencies for target. For every character in target, compute how many times it can be supplied from s using integer division: freqS[c] / freqTarget[c]. The smallest value across all required characters determines the number of complete copies you can form.
The key insight: the limiting character controls the answer. If target needs two a characters but s only contains four, you can build at most two copies regardless of other characters. Hash maps make counting straightforward and work well for general hash table problems involving string processing.
Approach 2: Array-based Frequency Calculation (O(n + m) time, O(1) space)
When the input is limited to lowercase English letters, a fixed array of size 26 replaces the hash map. Iterate through s and increment counts in countS[26]. Do the same for target using countT[26]. Then loop through the alphabet and compute the minimum value of countS[i] / countT[i] for characters that appear in target.
This version avoids hash lookups and uses constant memory. Array indexing is faster and predictable, which is why languages like C and C++ commonly use this pattern for counting-based problems. The algorithm remains linear because each string is scanned once and the alphabet scan is constant.
Recommended for interviews: Both approaches are optimal with O(n + m) time complexity. Interviewers typically expect the frequency-count insight quickly. Starting with the hash map approach shows clear reasoning and works for any character set. The array-based solution demonstrates optimization awareness when the alphabet size is fixed.
Approach 1: Frequency Count Method
The goal is to determine how many full copies of the target string can be formed using characters from the source string, s. To achieve this, count the frequency of each character in both s and target and use this count to determine the maximum number of complete targets that can be constructed using the characters from s.
This solution uses Python's collections.Counter to count the occurrences of each character in the strings s and target. By dividing the count of each character needed by the count available, we determine how many times we can use the available characters. The minimum of these values is our answer, as it represents the limiting factor in constructing the target.
Code
Python
JavaScript
Complexity
Time Complexity: O(n + m), where n is the length of s and m is the length of target.
Space Complexity: O(1), since the character set size is fixed and small (only lowercase English letters).
Approach 2: Array-based Frequency Calculation
This approach focuses on using an array of fixed size (equal to the number of lowercase English letters) for counting character frequencies. This avoids the overhead of dictionary-based implementations, potentially offering slight performance improvements by reducing dynamic memory allocation and more direct indexing.
This C example uses two fixed-size arrays of size 26 to count the occurrences of each character in s and target. The solution avoids the use of any dynamic data structures and uses basic array indexing, making it efficient given the constraints.
Complexity
Time Complexity: O(n + m), where n is the length of s and m is the length of target.
Space Complexity: O(1), given the fixed size of the frequency arrays.
Approach 3: Counting
We count the occurrences of each character in the strings s and target, denoted as cnt1 and cnt2. For each character in target, we calculate the number of times it appears in cnt1 divided by the number of times it appears in cnt2, and take the minimum value.
The time complexity is O(n + m), and the space complexity is O(|\Sigma|). Where n and m are the lengths of the strings s and target, respectively. And |\Sigma| is the size of the character set, which is 26 in this problem.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Frequency Count Method | Time Complexity: O(n + m), where n is the length of |
| Array-based Frequency Calculation | Time Complexity: O(n + m), where n is the length of |
| Counting | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Count with Hash Map | O(n + m) | O(k) | General case where characters may not be limited to a small alphabet |
| Array-based Frequency Counting | O(n + m) | O(1) | Best when input is lowercase English letters and memory/lookup speed matters |
Video Solution
Rearrange Characters to Make Target String | Leetcode 2287 | Maps | Contest 295 🔥🔥 • Coding Decoded • 1,817 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Rearrange Characters to Make Target String easy or hard?
Rearrange Characters to Make Target String Python/Java solution
How to solve Rearrange Characters to Make Target String in O(n)?
What is the best approach for Rearrange Characters to Make Target String?
Is Rearrange Characters to Make Target String asked at Google/Amazon/Meta?
What data structure is used in Rearrange Characters to Make Target String?
What is the time complexity of Rearrange Characters to Make Target String?
Ready to solve this problem?
Practice Rearrange Characters to Make Target String with our built-in code editor and test cases.
Practice on FleetCode