Watch 10 video solutions for Rearrange Characters to Make Target String, a easy level problem involving Hash Table, String, Counting. This walkthrough by Coding Decoded has 1,742 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 10s and target consist of lowercase English letters.
Note: This question is the same as 1189: Maximum Number of Balloons.
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 | 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 |