# Rearrange Characters to Make Target String
**Difficulty:** EASY
[External](https://leetcode.com/problems/rearrange-characters-to-make-target-string)
Canonical: https://scaleengineer.com/dsa/problems/rearrange-characters-to-make-target-string
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
---
## Problem
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 <= 100`
* `1 <= target.length <= 10`
* `s` and `target` consist of lowercase English letters.

**Note:** This question is the same as [ 1189: Maximum Number of Balloons.](https://leetcode.com/problems/maximum-number-of-balloons/description/)

# Approaches
## Brute-Force Simulation
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.
**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`.
**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 (`contains` and `remove` operations on an `ArrayList`) are slow, taking linear time for each operation.
### Explanation
```java
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;
    }
}
```
### Algorithm
1. Convert the source string `s` into a mutable data structure, like an `ArrayList` of characters.
2. Initialize a counter `copies` to 0.
3. Enter a loop that continues indefinitely (`while(true)`).
4. Inside the loop, assume a copy can be formed by setting a boolean flag `canFormThisCopy` to `true`.
5. Iterate through each character `tChar` of the `target` string.
6. For each `tChar`, check if it exists in the `ArrayList` of available characters. 
7. If it exists, remove one instance of it. This simulates using up the character.
8. If it does not exist, set `canFormThisCopy` to `false` and break the inner loop over `target`'s characters.
9. After the inner loop, if `canFormThisCopy` is still `true`, it means a full copy was formed, so increment `copies`.
10. If `canFormThisCopy` is `false`, it means we ran out of necessary characters, so we break the outer `while` loop.
11. Finally, return the total `copies` counted.

## Frequency Counting with HashMaps
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`.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
1. Create a `HashMap<Character, Integer>` called `sFreq` to store the frequency of each character in string `s`.
2. Iterate through `s` and populate `sFreq`.
3. Create a second `HashMap<Character, Integer>` called `targetFreq` for the string `target`.
4. Iterate through `target` and populate `targetFreq`.
5. Initialize a variable `minCopies` to a very large number (e.g., `Integer.MAX_VALUE`).
6. Iterate through each entry (character and its required count) in `targetFreq`.
7. For each required character, get its available count from `sFreq` (defaulting to 0 if not present).
8. Calculate the number of copies possible based on this single character: `possibleCopies = availableCount / requiredCount`.
9. Update `minCopies` to be the minimum of its current value and `possibleCopies`.
10. After checking all characters in `target`, `minCopies` will hold the answer. If `target` was empty, `minCopies` would not be updated, so return 0 in that case.

## Optimized Frequency Counting with Arrays
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
1. Create an integer array `sCounts` of size 26, initialized to all zeros. This will map 'a'->0, 'b'->1, etc.
2. Iterate through each character `c` in `s` and increment the count at the corresponding index: `sCounts[c - 'a']++`.
3. Create a second integer array `targetCounts` of size 26, also initialized to zeros.
4. Iterate through each character `c` in `target` and increment its count: `targetCounts[c - 'a']++`.
5. Initialize `minCopies = Integer.MAX_VALUE`.
6. Loop through the `targetCounts` array from index `i = 0` to `25`.
7. If `targetCounts[i]` is greater than 0, it means this character is needed.
8. Calculate `possibleCopies = sCounts[i] / targetCounts[i]` using integer division.
9. Update `minCopies = Math.min(minCopies, possibleCopies)`.
10. After the loop, `minCopies` holds the result. If it was never updated (e.g., `target` is empty), return 0.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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())

```