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.
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.
JavaScript
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).
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.
C++
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 | 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 |
Reorganize String - Tesla Interview Question - Leetcode 767 - Python • NeetCode • 57,555 views views
Watch 9 more video solutions →Practice Rearrange Characters to Make Target String with our built-in code editor and test cases.
Practice on FleetCode