class Solution {
public:
int rearrangeCharacters(string s, string target) {
}
};
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 <= 1001 <= target.length <= 10s 和 target 由小写英文字母组成原站题解
java 解法, 执行用时: 1 ms, 内存消耗: 39.8 MB, 提交时间: 2023-01-13 11:03:24
class Solution {
public int rearrangeCharacters(String s, String target) {
Map<Character, Integer> sCounts = new HashMap<Character, Integer>();
Map<Character, Integer> targetCounts = new HashMap<Character, Integer>();
int n = s.length(), m = target.length();
for (int i = 0; i < m; i++) {
char c = target.charAt(i);
targetCounts.put(c, targetCounts.getOrDefault(c, 0) + 1);
}
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if (targetCounts.containsKey(c)) {
sCounts.put(c, sCounts.getOrDefault(c, 0) + 1);
}
}
int ans = Integer.MAX_VALUE;
for (Map.Entry<Character, Integer> entry : targetCounts.entrySet()) {
char c = entry.getKey();
int count = entry.getValue();
int totalCount = sCounts.containsKey(c) ? sCounts.get(c) : 0;
ans = Math.min(ans, totalCount / count);
if (ans == 0) {
return 0;
}
}
return ans;
}
}
javascript 解法, 执行用时: 64 ms, 内存消耗: 41 MB, 提交时间: 2023-01-13 11:03:06
/**
* @param {string} s
* @param {string} target
* @return {number}
*/
var rearrangeCharacters = function(s, target) {
const sCounts = new Map();
const targetCounts = new Map();
const n = s.length, m = target.length;
for (let i = 0; i < m; i++) {
const c = target[i];
targetCounts.set(c, (targetCounts.get(c) || 0) + 1);
}
for (let i = 0; i < n; i++) {
const c = s[i];
if (targetCounts.has(c)) {
sCounts.set(c, (sCounts.get(c) || 0) + 1);
}
}
let ans = Number.MAX_VALUE;
for (const [c, count] of targetCounts.entries()) {
const totalCount = sCounts.has(c) ? sCounts.get(c) : 0;
ans = Math.min(ans, Math.floor(totalCount / count));
if (ans === 0) {
return 0;
}
}
return ans;
};
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-01-13 11:02:50
func rearrangeCharacters(s, target string) int {
var cntS, cntT [26]int
for _, c := range s {
cntS[c-'a']++
}
for _, c := range target {
cntT[c-'a']++
}
ans := len(s)
for i, c := range cntT {
if c > 0 {
ans = min(ans, cntS[i]/c)
if ans == 0 {
return 0
}
}
}
return ans
}
func min(a, b int) int { if a > b { return b }; return a }
python3 解法, 执行用时: 40 ms, 内存消耗: 15.1 MB, 提交时间: 2022-05-31 15:27:41
class Solution:
def rearrangeCharacters(self, s: str, target: str) -> int:
c1, c2 = Counter(s), Counter(target)
res = float('inf')
for c, cnt in c2.items():
res = min(res, c1[c]//cnt)
return res
python3 解法, 执行用时: 32 ms, 内存消耗: 15 MB, 提交时间: 2022-05-31 15:24:14
class Solution:
def rearrangeCharacters(self, s: str, target: str) -> int:
m = defaultdict(int)
for c in s:
m[c] += 1
ans = 0
while all(m[k] > 0 for k in target):
for c in target:
m[c] -= 1
if all(m[k] >= 0 for k in target):
ans += 1
return ans