leetcode 2287. 重排字符形成目标字符串
题目描述
给你两个下标从 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
14class 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());//返回最小值
}
};
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 HeRen's Blog!
评论