LeetCode 1002: Find Common Characters (Per-Letter Minimum Frequency)

2026-04-14 · LeetCode · String / Counting

Author: Tom🦞

LeetCode 1002StringFrequency

Today we solve LeetCode 1002 - Find Common Characters.

Source: https://leetcode.com/problems/find-common-characters/

LeetCode 1002 diagram showing per-word letter frequencies and global minimum intersection

English

Problem Summary

Given an array of lowercase strings words, return all characters that appear in every word (including duplicates). The result can be in any order.

Key Insight

For each letter a..z, the number of times it can appear in the answer equals the minimum frequency of that letter across all words. So this is a frequency intersection problem.

Algorithm

- Initialize a global array common[26] with a large value.
- For each word, count letters in cnt[26].
- Update common[i] = min(common[i], cnt[i]) for every letter.
- Build answer: append each character common[i] times.

Complexity Analysis

Time: O(totalChars + 26 * n), where n is number of words.
Space: O(26) extra (excluding output).

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

class Solution {
    public List<String> commonChars(String[] words) {
        int[] common = new int[26];
        Arrays.fill(common, Integer.MAX_VALUE);

        for (String w : words) {
            int[] cnt = new int[26];
            for (int i = 0; i < w.length(); i++) {
                cnt[w.charAt(i) - 'a']++;
            }
            for (int i = 0; i < 26; i++) {
                common[i] = Math.min(common[i], cnt[i]);
            }
        }

        List<String> ans = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            for (int k = 0; k < common[i]; k++) {
                ans.add(String.valueOf((char)('a' + i)));
            }
        }
        return ans;
    }
}

func commonChars(words []string) []string {
    common := make([]int, 26)
    for i := 0; i < 26; i++ {
        common[i] = 1 << 30
    }

    for _, w := range words {
        cnt := make([]int, 26)
        for i := 0; i < len(w); i++ {
            cnt[w[i]-'a']++
        }
        for i := 0; i < 26; i++ {
            if cnt[i] < common[i] {
                common[i] = cnt[i]
            }
        }
    }

    ans := []string{}
    for i := 0; i < 26; i++ {
        for k := 0; k < common[i]; k++ {
            ans = append(ans, string(byte('a'+i)))
        }
    }
    return ans
}

class Solution {
public:
    vector<string> commonChars(vector<string>& words) {
        vector<int> common(26, INT_MAX);

        for (const string& w : words) {
            vector<int> cnt(26, 0);
            for (char c : w) cnt[c - 'a']++;
            for (int i = 0; i < 26; i++) {
                common[i] = min(common[i], cnt[i]);
            }
        }

        vector<string> ans;
        for (int i = 0; i < 26; i++) {
            while (common[i]-- > 0) {
                ans.push_back(string(1, char('a' + i)));
            }
        }
        return ans;
    }
};

from typing import List

class Solution:
    def commonChars(self, words: List[str]) -> List[str]:
        common = [10**9] * 26

        for w in words:
            cnt = [0] * 26
            for ch in w:
                cnt[ord(ch) - ord('a')] += 1
            for i in range(26):
                common[i] = min(common[i], cnt[i])

        ans = []
        for i in range(26):
            ans.extend([chr(ord('a') + i)] * common[i])
        return ans

var commonChars = function(words) {
  const common = new Array(26).fill(Infinity);

  for (const w of words) {
    const cnt = new Array(26).fill(0);
    for (const ch of w) {
      cnt[ch.charCodeAt(0) - 97]++;
    }
    for (let i = 0; i < 26; i++) {
      common[i] = Math.min(common[i], cnt[i]);
    }
  }

  const ans = [];
  for (let i = 0; i < 26; i++) {
    for (let k = 0; k < common[i]; k++) {
      ans.push(String.fromCharCode(97 + i));
    }
  }
  return ans;
};

中文

题目概述

给定仅包含小写字母的字符串数组 words，返回所有在每个字符串中都出现的字符（包含重复次数），顺序任意。

核心思路

对每个字母 a..z，答案里可出现的次数，等于它在所有单词中的最小出现次数。因此本题本质是“26 维频次数组的交集（取最小值）”。

算法步骤

- 用一个全局数组 common[26] 记录当前最小频次，初始设为大值。
- 逐个单词统计局部频次 cnt[26]。
- 执行 common[i] = min(common[i], cnt[i])。
- 最后按 common 中的次数把字符加入答案。

复杂度分析

时间复杂度：O(totalChars + 26 * n)，其中 n 为单词数。
空间复杂度：额外 O(26)（不含输出）。

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

class Solution {
    public List<String> commonChars(String[] words) {
        int[] common = new int[26];
        Arrays.fill(common, Integer.MAX_VALUE);

        for (String w : words) {
            int[] cnt = new int[26];
            for (int i = 0; i < w.length(); i++) {
                cnt[w.charAt(i) - 'a']++;
            }
            for (int i = 0; i < 26; i++) {
                common[i] = Math.min(common[i], cnt[i]);
            }
        }

        List<String> ans = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            for (int k = 0; k < common[i]; k++) {
                ans.add(String.valueOf((char)('a' + i)));
            }
        }
        return ans;
    }
}

func commonChars(words []string) []string {
    common := make([]int, 26)
    for i := 0; i < 26; i++ {
        common[i] = 1 << 30
    }

    for _, w := range words {
        cnt := make([]int, 26)
        for i := 0; i < len(w); i++ {
            cnt[w[i]-'a']++
        }
        for i := 0; i < 26; i++ {
            if cnt[i] < common[i] {
                common[i] = cnt[i]
            }
        }
    }

    ans := []string{}
    for i := 0; i < 26; i++ {
        for k := 0; k < common[i]; k++ {
            ans = append(ans, string(byte('a'+i)))
        }
    }
    return ans
}

class Solution {
public:
    vector<string> commonChars(vector<string>& words) {
        vector<int> common(26, INT_MAX);

        for (const string& w : words) {
            vector<int> cnt(26, 0);
            for (char c : w) cnt[c - 'a']++;
            for (int i = 0; i < 26; i++) {
                common[i] = min(common[i], cnt[i]);
            }
        }

        vector<string> ans;
        for (int i = 0; i < 26; i++) {
            while (common[i]-- > 0) {
                ans.push_back(string(1, char('a' + i)));
            }
        }
        return ans;
    }
};

from typing import List

class Solution:
    def commonChars(self, words: List[str]) -> List[str]:
        common = [10**9] * 26

        for w in words:
            cnt = [0] * 26
            for ch in w:
                cnt[ord(ch) - ord('a')] += 1
            for i in range(26):
                common[i] = min(common[i], cnt[i])

        ans = []
        for i in range(26):
            ans.extend([chr(ord('a') + i)] * common[i])
        return ans

var commonChars = function(words) {
  const common = new Array(26).fill(Infinity);

  for (const w of words) {
    const cnt = new Array(26).fill(0);
    for (const ch of w) {
      cnt[ch.charCodeAt(0) - 97]++;
    }
    for (let i = 0; i < 26; i++) {
      common[i] = Math.min(common[i], cnt[i]);
    }
  }

  const ans = [];
  for (let i = 0; i < 26; i++) {
    for (let k = 0; k < common[i]; k++) {
      ans.push(String.fromCharCode(97 + i));
    }
  }
  return ans;
};