Easy

题目描述

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

请你返回从 s 中取出字符重新排列后，能够形成 target 的 最大 副本数。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

注意： 这道题和第 1189 题：“气球” 的最大数量相同。

解题思路

这道题的核心思路是字符频次统计和瓶颈分析。

要形成目标字符串 target 的副本，我们需要确保有足够的字符。具体步骤如下：

  1. 统计字符频次：分别统计字符串 s 和 target 中每个字符的出现次数。

  2. 找到瓶颈字符：对于 target 中的每个字符，计算我们最多能形成多少份：

    • 如果字符 c 在 s 中出现 x 次，在 target 中出现 y 次
    • 那么字符 c 最多能支持形成 floor(x/y) 份 target

  3. 取最小值：所有字符中支持的最少副本数就是答案，因为任何一个字符不足都会限制整体的副本数量。

这种思路类似于"木桶效应"，最短的木板决定了木桶的容量。在这里，出现频次相对最少的字符决定了能形成的最大副本数。

时间复杂度方面，我们只需要遍历两个字符串各一次进行统计，然后遍历 target 的字符集合，整体是线性时间复杂度。

代码实现

class Solution {
public:
    int rearrangeCharacters(string s, string target) {
        unordered_map<char, int> sCount, targetCount;
        
        // 统计 s 中每个字符的频次
        for (char c : s) {
            sCount[c]++;
        }
        
        // 统计 target 中每个字符的频次
        for (char c : target) {
            targetCount[c]++;
        }
        
        int result = INT_MAX;
        
        // 对于 target 中的每个字符，计算最多能形成多少份
        for (auto& pair : targetCount) {
            char c = pair.first;
            int needed = pair.second;
            int available = sCount[c];
            
            result = min(result, available / needed);
        }
        
        return result;
    }
};

class Solution:
    def rearrangeCharacters(self, s: str, target: str) -> int:
        from collections import Counter
        
        s_count = Counter(s)
        target_count = Counter(target)
        
        result = float('inf')
        
        # 对于 target 中的每个字符，计算最多能形成多少份
        for char, needed in target_count.items():
            available = s_count.get(char, 0)
            result = min(result, available // needed)
        
        return result

public class Solution {
    public int RearrangeCharacters(string s, string target) {
        Dictionary<char, int> sCount = new Dictionary<char, int>();
        Dictionary<char, int> targetCount = new Dictionary<char, int>();
        
        // 统计 s 中每个字符的频次
        foreach (char c in s) {
            sCount[c] = sCount.GetValueOrDefault(c, 0) + 1;
        }
        
        // 统计 target 中每个字符的频次
        foreach (char c in target) {
            targetCount[c] = targetCount.GetValueOrDefault(c, 0) + 1;
        }
        
        int result = int.MaxValue;
        
        // 对于 target 中的每个字符，计算最多能形成多少份
        foreach (var pair in targetCount) {
            char c = pair.Key;
            int needed = pair.Value;
            int available = sCount.GetValueOrDefault(c, 0);
            
            result = Math.Min(result, available / needed);
        }
        
        return result;
    }
}

var rearrangeCharacters = function(s, target) {
    const sCount = new Map();
    const targetCount = new Map();
    
    // 统计 s 中每个字符的频次
    for (const c of s) {
        sCount.set(c, (sCount.get(c) || 0) + 1);
    }
    
    // 统计 target 中每个字符的频次
    for (const c of target) {
        targetCount.set(c, (targetCount.get(c) || 0) + 1);
    }
    
    let result = Infinity;
    
    // 对于 target 中的每个字符，计算最多能形成多少份
    for (const [char, needed] of targetCount) {
        const available = sCount.get(char) || 0;
        result = Math.min(result, Math.floor(available / needed));
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
哈希表统计O(n + m + k)O(k)

其中：

  • n 是字符串 s 的长度
  • m 是字符串 target 的长度
  • k 是 target 中不同字符的数量（最多26个小写字母）

相关题目