题目描述

leetcode2287. 重排字符形成目标字符串

给你两个下标从 0 开始的字符串 s 和 target 。你可以从 s 取出一些字符并将其重排，得到若干新的字符串。

从 s 中取出字符并重新排列，返回可以形成 target 的 最大 副本数。

 

示例 1：

输入：s = "ilovecodingonleetcode", target = "code"
输出：2
解释：
对于 "code" 的第 1 个副本，选取下标为 4 、5 、6 和 7 的字符。
对于 "code" 的第 2 个副本，选取下标为 17 、18 、19 和 20 的字符。
形成的字符串分别是 "ecod" 和 "code" ，都可以重排为 "code" 。
可以形成最多 2 个 "code" 的副本，所以返回 2 。

示例 2：

输入：s = "abcba", target = "abc"
输出：1
解释：
选取下标为 0 、1 和 2 的字符，可以形成 "abc" 的 1 个副本。 
可以形成最多 1 个 "abc" 的副本，所以返回 1 。
注意，尽管下标 3 和 4 分别有额外的 'a' 和 'b' ，但不能重用下标 2 处的 'c' ，所以无法形成 "abc" 的第 2 个副本。

示例 3：

输入：s = "abbaccaddaeea", target = "aaaaa"
输出：1
解释：
选取下标为 0 、3 、6 、9 和 12 的字符，可以形成 "aaaaa" 的 1 个副本。
可以形成最多 1 个 "aaaaa" 的副本，所以返回 1 。

 

提示：

  • 1 <= s.length <= 100
  • 1 <= target.length <= 10
  • s 和 target 由小写英文字母组成

题解——哈希表+短板效应

图片

由于我们可以对字符重新排列,那么只要数目足够,就认为得到了副本
考虑用哈希表对s和target中的字符计数,决定能形成的副本数是对应字符的最小倍数,即短板效应
比如s="aabbbccc",target="abc",a的倍数为2,b为3,c为3,那么最终能形成两个副本
所以再构建一个数组存放各个字符的倍数,返回其中的最小元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int rearrangeCharacters(string s, string target) {
        unordered_map<char,int> sCnt,tCnt;
        for(auto ch:target)//对target计数
            ++tCnt[ch];
        for(auto ch:s)//对s计数
            ++sCnt[ch];
        vector<int> times;
        for(auto p:tCnt)//保存倍数
            times.push_back(sCnt[p.first]/p.second);
        return *min_element(times.begin(),times.end());//返回最小值
    }
};