Rearrange Characters to Make Target 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 _themaximum number of copies of _target that can be formed by taking letters froms and rearranging them.

Examples

Example 1

1
2
3
4
5
6
7


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

1
2
3
4
5
6


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

1
2
3
4
5


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/)

Solution

Method 1 – Count and Divide

Intuition

Count the frequency of each letter in s and in target. The answer is the minimum number of times we can use the letters in s to form target, i.e., for each letter in target, how many times it appears in s divided by how many times it is needed.

Approach

Count the frequency of each letter in s and in target.
For each letter in target, compute how many times it can be used (count in s // count in target).
The answer is the minimum of these values.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution {
public:
    int rearrangeCharacters(string s, string target) {
        vector<int> cntS(26), cntT(26);
        for (char c : s) cntS[c - 'a']++;
        for (char c : target) cntT[c - 'a']++;
        int ans = INT_MAX;
        for (int i = 0; i < 26; ++i) {
            if (cntT[i]) ans = min(ans, cntS[i] / cntT[i]);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


func rearrangeCharacters(s, target string) int {
    cntS, cntT := [26]int{}, [26]int{}
    for _, c := range s { cntS[c-'a']++ }
    for _, c := range target { cntT[c-'a']++ }
    ans := 1<<30
    for i := 0; i < 26; i++ {
        if cntT[i] > 0 {
            if cntS[i]/cntT[i] < ans {
                ans = cntS[i]/cntT[i]
            }
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution {
    public int rearrangeCharacters(String s, String target) {
        int[] cntS = new int[26], cntT = new int[26];
        for (char c : s.toCharArray()) cntS[c - 'a']++;
        for (char c : target.toCharArray()) cntT[c - 'a']++;
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < 26; ++i) {
            if (cntT[i] > 0) ans = Math.min(ans, cntS[i] / cntT[i]);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution {
    fun rearrangeCharacters(s: String, target: String): Int {
        val cntS = IntArray(26)
        val cntT = IntArray(26)
        for (c in s) cntS[c - 'a']++
        for (c in target) cntT[c - 'a']++
        var ans = Int.MAX_VALUE
        for (i in 0 until 26) {
            if (cntT[i] > 0) ans = minOf(ans, cntS[i] / cntT[i])
        }
        return ans
    }
}

1
2
3
4
5
6


class Solution:
    def rearrangeCharacters(self, s: str, target: str) -> int:
        from collections import Counter
        cntS = Counter(s)
        cntT = Counter(target)
        return min(cntS[c] // cntT[c] for c in cntT)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


use std::cmp::min;
impl Solution {
    pub fn rearrange_characters(s: String, target: String) -> i32 {
        let mut cnt_s = [0; 26];
        let mut cnt_t = [0; 26];
        for c in s.chars() { cnt_s[(c as u8 - b'a') as usize] += 1; }
        for c in target.chars() { cnt_t[(c as u8 - b'a') as usize] += 1; }
        let mut ans = i32::MAX;
        for i in 0..26 {
            if cnt_t[i] > 0 {
                ans = min(ans, cnt_s[i] / cnt_t[i]);
            }
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution {
    rearrangeCharacters(s: string, target: string): number {
        const cntS = Array(26).fill(0), cntT = Array(26).fill(0);
        for (const c of s) cntS[c.charCodeAt(0) - 97]++;
        for (const c of target) cntT[c.charCodeAt(0) - 97]++;
        let ans = Number.MAX_SAFE_INTEGER;
        for (let i = 0; i < 26; ++i) {
            if (cntT[i] > 0) ans = Math.min(ans, Math.floor(cntS[i] / cntT[i]));
        }
        return ans;
    }
}

Complexity

⏰ Time complexity: O(n + m), where n = len(s), m = len(target), since we count and check each letter.
🧺 Space complexity: O(1), since the alphabet size is constant (26).

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Count and Divide#

Intuition#

Approach#

Code#

Complexity#