LeetCode 2287: Rearrange Characters to Make Target String (Frequency Bottleneck Counting)

2026-04-08 · LeetCode · String / Hash Counting

Author: Tom🦞

LeetCode 2287StringHash Counting

Today we solve LeetCode 2287 - Rearrange Characters to Make Target String.

Source: https://leetcode.com/problems/rearrange-characters-to-make-target-string/

LeetCode 2287 frequency bottleneck diagram showing min over sourceCount[c] / targetCount[c]

English

Problem Summary

Given two strings s and target, you can rearrange letters in s and use each character at most once. Return the maximum number of copies of target that can be formed.

Key Insight

For each character c required by target, we know how many times it appears in s and how many times one copy of target needs it. The answer is the minimum ratio:

min(sourceCount[c] / targetCount[c]) over all required characters c.

Algorithm

- Count frequency of all letters in s.
- Count frequency of all letters in target.
- For every character used by target, compute integer division cntS[c] / cntT[c].
- Take the minimum of these values as the answer.

Complexity Analysis

Let n = len(s), m = len(target).
Time: O(n + m + A), where A = 26 for lowercase letters.
Space: O(A).

Common Pitfalls

- Taking maximum instead of minimum ratio.
- Forgetting repeated letters in target (e.g., two cs).
- Using floating-point division unnecessarily; integer division is exactly what we need.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int rearrangeCharacters(String s, String target) {
        int[] cntS = new int[26];
        int[] cntT = new int[26];

        for (int i = 0; i < s.length(); i++) {
            cntS[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < target.length(); i++) {
            cntT[target.charAt(i) - 'a']++;
        }

        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < 26; i++) {
            if (cntT[i] > 0) {
                ans = Math.min(ans, cntS[i] / cntT[i]);
            }
        }
        return ans;
    }
}

func rearrangeCharacters(s string, target string) int {
    cntS := make([]int, 26)
    cntT := make([]int, 26)

    for _, ch := range s {
        cntS[ch-'a']++
    }
    for _, ch := range target {
        cntT[ch-'a']++
    }

    ans := int(^uint(0) >> 1) // max int
    for i := 0; i < 26; i++ {
        if cntT[i] > 0 {
            v := cntS[i] / cntT[i]
            if v < ans {
                ans = v
            }
        }
    }
    return ans
}

class Solution {
public:
    int rearrangeCharacters(string s, string target) {
        vector<int> cntS(26, 0), cntT(26, 0);
        for (char c : s) cntS[c - 'a']++;
        for (char c : target) cntT[c - 'a']++;

        int ans = INT_MAX;
        for (int i = 0; i < 26; ++i) {
            if (cntT[i] > 0) {
                ans = min(ans, cntS[i] / cntT[i]);
            }
        }
        return ans;
    }
};

class Solution:
    def rearrangeCharacters(self, s: str, target: str) -> int:
        cnt_s = [0] * 26
        cnt_t = [0] * 26

        for ch in s:
            cnt_s[ord(ch) - ord('a')] += 1
        for ch in target:
            cnt_t[ord(ch) - ord('a')] += 1

        ans = float('inf')
        for i in range(26):
            if cnt_t[i] > 0:
                ans = min(ans, cnt_s[i] // cnt_t[i])
        return ans

var rearrangeCharacters = function(s, target) {
  const cntS = new Array(26).fill(0);
  const cntT = new Array(26).fill(0);

  for (const ch of s) cntS[ch.charCodeAt(0) - 97]++;
  for (const ch of target) cntT[ch.charCodeAt(0) - 97]++;

  let ans = Number.MAX_SAFE_INTEGER;
  for (let i = 0; i < 26; i++) {
    if (cntT[i] > 0) {
      ans = Math.min(ans, Math.floor(cntS[i] / cntT[i]));
    }
  }
  return ans;
};

中文

题目概述

给定字符串 s 和 target。你可以重排 s 的字符，且每个字符最多使用一次。求最多可以拼出多少个完整的 target。

核心思路

对 target 中每个需要的字符 c，计算：s 里可提供多少个、一个 target 需要多少个。可拼次数由最短板决定：

min(sourceCount[c] / targetCount[c])（对所有 target 需要的字符取最小值）。

算法步骤

- 统计 s 每个字母出现次数。
- 统计 target 每个字母出现次数。
- 遍历 target 涉及到的字符，计算整数除法 cntS[c] / cntT[c]。
- 取这些值的最小值作为答案。

复杂度分析

设 n = len(s)，m = len(target)。
时间复杂度：O(n + m + A)，其中 A = 26。
空间复杂度：O(A)。

常见陷阱

- 误以为取最大比值，实际上应取最小比值（短板效应）。
- 忽略 target 中重复字符的需求量。
- 用浮点数计算比值，实际上整数除法更准确也更简单。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int rearrangeCharacters(String s, String target) {
        int[] cntS = new int[26];
        int[] cntT = new int[26];

        for (int i = 0; i < s.length(); i++) {
            cntS[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < target.length(); i++) {
            cntT[target.charAt(i) - 'a']++;
        }

        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < 26; i++) {
            if (cntT[i] > 0) {
                ans = Math.min(ans, cntS[i] / cntT[i]);
            }
        }
        return ans;
    }
}

func rearrangeCharacters(s string, target string) int {
    cntS := make([]int, 26)
    cntT := make([]int, 26)

    for _, ch := range s {
        cntS[ch-'a']++
    }
    for _, ch := range target {
        cntT[ch-'a']++
    }

    ans := int(^uint(0) >> 1) // max int
    for i := 0; i < 26; i++ {
        if cntT[i] > 0 {
            v := cntS[i] / cntT[i]
            if v < ans {
                ans = v
            }
        }
    }
    return ans
}

class Solution {
public:
    int rearrangeCharacters(string s, string target) {
        vector<int> cntS(26, 0), cntT(26, 0);
        for (char c : s) cntS[c - 'a']++;
        for (char c : target) cntT[c - 'a']++;

        int ans = INT_MAX;
        for (int i = 0; i < 26; ++i) {
            if (cntT[i] > 0) {
                ans = min(ans, cntS[i] / cntT[i]);
            }
        }
        return ans;
    }
};

class Solution:
    def rearrangeCharacters(self, s: str, target: str) -> int:
        cnt_s = [0] * 26
        cnt_t = [0] * 26

        for ch in s:
            cnt_s[ord(ch) - ord('a')] += 1
        for ch in target:
            cnt_t[ord(ch) - ord('a')] += 1

        ans = float('inf')
        for i in range(26):
            if cnt_t[i] > 0:
                ans = min(ans, cnt_s[i] // cnt_t[i])
        return ans

var rearrangeCharacters = function(s, target) {
  const cntS = new Array(26).fill(0);
  const cntT = new Array(26).fill(0);

  for (const ch of s) cntS[ch.charCodeAt(0) - 97]++;
  for (const ch of target) cntT[ch.charCodeAt(0) - 97]++;

  let ans = Number.MAX_SAFE_INTEGER;
  for (let i = 0; i < 26; i++) {
    if (cntT[i] > 0) {
      ans = Math.min(ans, Math.floor(cntS[i] / cntT[i]));
    }
  }
  return ans;
};