Find Common Characters

easy hash map string frequency count

Problem

Given a string array words, return an array of all characters that show up in all strings within the words (including duplicates). You may return the answer in any order.

Inputwords = ["bella", "label", "roller"]

Output["e", "l", "l"]

'l' appears at least twice in every word, and 'e' appears at least once, so the common multiset is e, l, l.

words (comma-separated, lowercase)

def common_chars(words):
    common = [0] * 26
    for i, c in enumerate(words[0]):
        common[ord(c) - 97] += 1
    for w in words[1:]:
        cur = [0] * 26
        for c in w:
            cur[ord(c) - 97] += 1
        for k in range(26):
            common[k] = min(common[k], cur[k])
    res = []
    for k in range(26):
        res += [chr(k + 97)] * common[k]
    return res

function commonChars(words) {
  const common = new Array(26).fill(0);
  for (const c of words[0]) common[c.charCodeAt(0) - 97]++;
  for (let i = 1; i < words.length; i++) {
    const cur = new Array(26).fill(0);
    for (const c of words[i]) cur[c.charCodeAt(0) - 97]++;
    for (let k = 0; k < 26; k++) common[k] = Math.min(common[k], cur[k]);
  }
  const res = [];
  for (let k = 0; k < 26; k++)
    for (let j = 0; j < common[k]; j++) res.push(String.fromCharCode(k + 97));
  return res;
}

class Solution {
    public List<String> commonChars(String[] words) {
        int[] common = new int[26];
        for (char c : words[0].toCharArray()) common[c - 'a']++;
        for (int i = 1; i < words.length; i++) {
            int[] cur = new int[26];
            for (char c : words[i].toCharArray()) cur[c - 'a']++;
            for (int k = 0; k < 26; k++) common[k] = Math.min(common[k], cur[k]);
        }
        List<String> res = new ArrayList<>();
        for (int k = 0; k < 26; k++)
            for (int j = 0; j < common[k]; j++) res.add(String.valueOf((char)(k + 'a')));
        return res;
    }
}

vector<string> commonChars(vector<string>& words) {
    vector<int> common(26, 0);
    for (char c : words[0]) common[c - 'a']++;
    for (int i = 1; i < (int)words.size(); i++) {
        vector<int> cur(26, 0);
        for (char c : words[i]) cur[c - 'a']++;
        for (int k = 0; k < 26; k++) common[k] = min(common[k], cur[k]);
    }
    vector<string> res;
    for (int k = 0; k < 26; k++)
        for (int j = 0; j < common[k]; j++) res.push_back(string(1, 'a' + k));
    return res;
}

Explanation

A letter belongs in the answer once for every time it appears in all the words. So the count we keep for each letter is its minimum frequency across every word.

We start with a 26-slot frequency array common seeded from the first word. Then for each later word we count its own letters into cur and take, slot by slot, common[k] = min(common[k], cur[k]). Any letter missing from a word drops its running count toward zero, knocking it out.

After processing every word, common[k] holds how many copies of letter k survive in all words. We then expand the answer by emitting each letter that many times.

Example: ["bella", "label", "roller"]. The letter l appears at least twice in each word, so it stays with count 2; e appears at least once everywhere, so it stays with count 1. Expanding gives ["e", "l", "l"].

Using a fixed 26-slot array keeps the extra space tiny, and we touch each character only once.

Time: O(n · m) Space: O(1)