Rearrange Characters to Make Target String
EasyPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the process of forming copies of the target string. It repeatedly tries to construct one copy of target by finding and "using up" characters from s. We maintain a list of available characters from s and, for each copy we try to make, we check for and remove the required characters from this list. We count how many times we can successfully complete this process.
Algorithm
- Convert the source string
sinto a mutable data structure, like anArrayListof characters. - Initialize a counter
copiesto 0. - Enter a loop that continues indefinitely (
while(true)). - Inside the loop, assume a copy can be formed by setting a boolean flag
canFormThisCopytotrue. - Iterate through each character
tCharof thetargetstring. - For each
tChar, check if it exists in theArrayListof available characters. - If it exists, remove one instance of it. This simulates using up the character.
- If it does not exist, set
canFormThisCopytofalseand break the inner loop overtarget's characters. - After the inner loop, if
canFormThisCopyis stilltrue, it means a full copy was formed, so incrementcopies. - If
canFormThisCopyisfalse, it means we ran out of necessary characters, so we break the outerwhileloop. - Finally, return the total
copiescounted.
Walkthrough
import java.util.ArrayList;import java.util.List; class Solution { public int rearrangeCharacters(String s, String target) { List<Character> sChars = new ArrayList<>(); for (char c : s.toCharArray()) { sChars.add(c); } int copies = 0; while (true) { boolean possible = true; // Try to form one copy of the target for (char tChar : target.toCharArray()) { // Find and remove the required character from sChars if (sChars.contains(tChar)) { sChars.remove(Character.valueOf(tChar)); // remove by object, not index } else { // Character not available, cannot form this copy possible = false; break; } } if (possible) { // Successfully formed one copy copies++; } else { // Cannot form any more copies, exit the loop break; } } return copies; }}Complexity
Time
O(K * M * N), where N is `s.length()`, M is `target.length()`, and K is the number of copies made. In the worst case, K can be up to `N/M`, leading to a time complexity of O(N^2). Each `contains` and `remove` operation on the list takes O(N) time.
Space
O(N), where N is the length of string `s`. This is required to store the `ArrayList` of characters from `s`.
Trade-offs
Pros
Intuitive and easy to understand as it directly models the problem statement.
Cons
Very inefficient, especially for larger strings. The time complexity is quadratic in the worst case.
Repeatedly scanning and modifying a list (
containsandremoveoperations on anArrayList) are slow, taking linear time for each operation.
A much more efficient approach is to count character frequencies instead of simulating the process. The core idea is that the number of target copies we can form is limited by the character that is least available relative to its requirement. We use HashMaps to store the character counts for both s and target.
Algorithm
- Create a
HashMap<Character, Integer>calledsFreqto store the frequency of each character in strings. - Iterate through
sand populatesFreq. - Create a second
HashMap<Character, Integer>calledtargetFreqfor the stringtarget. - Iterate through
targetand populatetargetFreq. - Initialize a variable
minCopiesto a very large number (e.g.,Integer.MAX_VALUE). - Iterate through each entry (character and its required count) in
targetFreq. - For each required character, get its available count from
sFreq(defaulting to 0 if not present). - Calculate the number of copies possible based on this single character:
possibleCopies = availableCount / requiredCount. - Update
minCopiesto be the minimum of its current value andpossibleCopies. - After checking all characters in
target,minCopieswill hold the answer. Iftargetwas empty,minCopieswould not be updated, so return 0 in that case.
Walkthrough
First, we create a frequency map for all characters in s to count our available resources. Second, we create a frequency map for target to know what's required for one copy. Then, for each character required by target, we calculate how many copies we can make by dividing its count in s by its count in target. The overall maximum number of copies is the minimum of these values, as this represents the bottleneck character.
import java.util.HashMap;import java.util.Map; class Solution { public int rearrangeCharacters(String s, String target) { Map<Character, Integer> sFreq = new HashMap<>(); for (char c : s.toCharArray()) { sFreq.put(c, sFreq.getOrDefault(c, 0) + 1); } Map<Character, Integer> targetFreq = new HashMap<>(); for (char c : target.toCharArray()) { targetFreq.put(c, targetFreq.getOrDefault(c, 0) + 1); } int minCopies = Integer.MAX_VALUE; for (Map.Entry<Character, Integer> entry : targetFreq.entrySet()) { char c = entry.getKey(); int requiredCount = entry.getValue(); int availableCount = sFreq.getOrDefault(c, 0); minCopies = Math.min(minCopies, availableCount / requiredCount); } return minCopies == Integer.MAX_VALUE ? 0 : minCopies; }}Complexity
Time
O(N + M), where N is the length of `s` and M is the length of `target`. Populating the frequency maps takes O(N) and O(M) time respectively. The final loop runs at most K times (where K is the alphabet size), which is constant.
Space
O(K), where K is the number of unique characters in the alphabet. Since the alphabet size is constant (e.g., 26 for lowercase English letters), this is considered O(1) space.
Trade-offs
Pros
Significantly more efficient than the brute-force approach with a linear time complexity.
Flexible and works for any character set, not just lowercase English letters.
Cons
Slightly more memory and time overhead due to hashing and object creation (
Character,Integer) compared to a simple array-based approach.
This is the most optimal approach, building upon the frequency counting idea. Since the problem specifies that the strings consist only of lowercase English letters, we can use a simple array of size 26 as a highly efficient frequency map instead of a HashMap. This avoids the overhead of hashing and object creation, making it faster and more memory-efficient.
Algorithm
- Create an integer array
sCountsof size 26, initialized to all zeros. This will map 'a'->0, 'b'->1, etc. - Iterate through each character
cinsand increment the count at the corresponding index:sCounts[c - 'a']++. - Create a second integer array
targetCountsof size 26, also initialized to zeros. - Iterate through each character
cintargetand increment its count:targetCounts[c - 'a']++. - Initialize
minCopies = Integer.MAX_VALUE. - Loop through the
targetCountsarray from indexi = 0to25. - If
targetCounts[i]is greater than 0, it means this character is needed. - Calculate
possibleCopies = sCounts[i] / targetCounts[i]using integer division. - Update
minCopies = Math.min(minCopies, possibleCopies). - After the loop,
minCopiesholds the result. If it was never updated (e.g.,targetis empty), return 0.
Walkthrough
The logic is identical to the HashMap approach, but the data structure for frequency counting is an array. We use two arrays of size 26, one for s and one for target, where the index i corresponds to the character 'a' + i. After populating these count arrays, we find the bottleneck by iterating through the 26 possible characters and calculating the minimum number of copies we can form.
class Solution { public int rearrangeCharacters(String s, String target) { int[] sCounts = new int[26]; for (char c : s.toCharArray()) { sCounts[c - 'a']++; } int[] targetCounts = new int[26]; for (char c : target.toCharArray()) { targetCounts[c - 'a']++; } int minCopies = Integer.MAX_VALUE; for (int i = 0; i < 26; i++) { // Check only for characters that are present in the target string if (targetCounts[i] > 0) { // Calculate how many times we can form the target with this character int possibleCopies = sCounts[i] / targetCounts[i]; minCopies = Math.min(minCopies, possibleCopies); } } // If minCopies was never updated (e.g., target is empty), result should be 0. // Otherwise, it holds the maximum number of copies. return minCopies == Integer.MAX_VALUE ? 0 : minCopies; }}Complexity
Time
O(N + M), where N is the length of `s` and M is the length of `target`. The two loops for counting take O(N) and O(M), and the final loop is constant time, O(26).
Space
O(1), as we only use two arrays of a fixed size (26), which does not depend on the input string lengths.
Trade-offs
Pros
Most efficient solution in terms of both time and space.
Uses primitive arrays for frequency counting, which is faster than HashMaps due to direct memory access and no boxing/unboxing overhead.
Cons
This specific implementation is tailored to a fixed character set (lowercase English letters). It would require modification to handle other character sets like uppercase letters, numbers, or Unicode characters.
Solutions
Solution
class Solution {public int rearrangeCharacters(String s, String target) { int[] cnt1 = new int[26]; int[] cnt2 = new int[26]; for (int i = 0; i < s.length(); ++i) { ++cnt1[s.charAt(i) - 'a']; } for (int i = 0; i < target.length(); ++i) { ++cnt2[target.charAt(i) - 'a']; } int ans = 100; for (int i = 0; i < 26; ++i) { if (cnt2[i] > 0) { ans = Math.min(ans, cnt1[i] / cnt2[i]); } } return ans; }}class Solution {public: int rearrangeCharacters(string s, string target) { int cnt1[26]{}; int cnt2[26]{}; for (char &c : s) { ++cnt1[c - 'a']; } for (char &c : target) { ++cnt2[c - 'a']; } int ans = 100; for (int i = 0; i < 26; ++i) { if (cnt2[i]) { ans = min(ans, cnt1[i] / cnt2[i]); } } return ans; }};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())Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.