2287. Rearrange Characters to Make Target String Easy

1/**
2 * [2287] Rearrange Characters to Make Target String
3 *
4 * You are given two 0-indexed strings s and target. You can take some letters from s and rearrange them to form new strings.
5 * Return the maximum number of copies of target that can be formed by taking letters from s and rearranging them.
6 *  
7 * Example 1:
8 *
9 * Input: s = "ilovecodingonleetcode", target = "code"
10 * Output: 2
11 * Explanation:
12 * For the first copy of "code", take the letters at indices 4, 5, 6, and 7.
13 * For the second copy of "code", take the letters at indices 17, 18, 19, and 20.
14 * The strings that are formed are "ecod" and "code" which can both be rearranged into "code".
15 * We can make at most two copies of "code", so we return 2.
16 *
17 * Example 2:
18 *
19 * Input: s = "abcba", target = "abc"
20 * Output: 1
21 * Explanation:
22 * We can make one copy of "abc" by taking the letters at indices 0, 1, and 2.
23 * We can make at most one copy of "abc", so we return 1.
24 * 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".
25 *
26 * Example 3:
27 *
28 * Input: s = "abbaccaddaeea", target = "aaaaa"
29 * Output: 1
30 * Explanation:
31 * We can make one copy of "aaaaa" by taking the letters at indices 0, 3, 6, 9, and 12.
32 * We can make at most one copy of "aaaaa", so we return 1.
33 *
34 *  
35 * Constraints:
36 *
37 * 1 <= s.length <= 100
38 * 1 <= target.length <= 10
39 * s and target consist of lowercase English letters.
40 *
41 */
42pub struct Solution {}
43
44// problem: https://leetcode.com/problems/rearrange-characters-to-make-target-string/
45// discuss: https://leetcode.com/problems/rearrange-characters-to-make-target-string/discuss/?currentPage=1&orderBy=most_votes&query=
46
47// submission codes start here
48use std::cmp;
49impl Solution {
50    pub fn rearrange_characters(s: String, target: String) -> i32 {
51        let source_counts =
52            s.chars()
53                .map(|c| c as usize - 'a' as usize)
54                .fold(vec![0; 26], |mut acc, e| {
55                    acc[e] += 1;
56                    acc
57                });
58        let target_counts =
59            target
60                .chars()
61                .map(|c| c as usize - 'a' as usize)
62                .fold(vec![0; 26], |mut acc, e| {
63                    acc[e] += 1;
64                    acc
65                });
66
67        let mut result = i32::MAX;
68        for (i, e) in target_counts.iter().enumerate() {
69            if *e == 0 {
70                continue;
71            }
72            result = cmp::min(result, source_counts[i] / *e);
73        }
74        result
75    }
76}
77
78// submission codes end
79
80#[cfg(test)]
81mod tests {
82    use super::*;
83
84    #[test]
85    fn test_2287() {
86        assert_eq!(
87            Solution::rearrange_characters("ilovecodingonleetcode".into(), "code".into()),
88            2
89        );
90        assert_eq!(
91            Solution::rearrange_characters("abbaccaddaeea".into(), "aaaa".into()),
92            1
93        );
94        assert_eq!(
95            Solution::rearrange_characters("abcba".into(), "abc".into()),
96            1
97        );
98    }
99}
100