「每日LeetCode」2022年6月2日

本文最后更新于：2023年3月19日 晚上

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

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 由小写英文字母组成

思路

两个 hash 表分别存储目标单词每个字母出现次数的 map1，以及字符 S 每个字母出现次数的 map2，map2 仅记录在 map1 中的字母。一直取目标单词，计数，直到 map2 中不能再取。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * @param {string} s
 * @param {string} target
 * @return {number}
 */
var rearrangeCharacters = function (s, target) {
  const map = {},
    map2 = {};
  for (const char of target) {
    if (map[char]) map[char]++;
    else map[char] = 1;
  }
  for (const char of s) {
    if (!map[char]) continue;
    if (map2[char]) map2[char]++;
    else map2[char] = 1;
  }
  let count = 0,
    temp = 0,
    flag;
  while (true) {
    for (const char in map) {
      const num = map[char];
      if (!map2[char] || map2[char] < num) {
        flag = true;
        break;
      }
      map2[char] -= num;
      temp += num;
    }
    if (flag) break;
    if (temp === target.length) {
      count++;
      temp = 0;
    }
  }
  return count;
};