3.32 Find Common Characters

3.32.1 Problem Metadata

3.32.2 Description

Given an array of lowercase strings, return a lc-list of all characters that appear in every string (including duplicates). Order does not matter.

3.32.3 Examples

Input: ["bella","label","roller"]
Output: ["e","l","l"]

3.32.4 Constraints

  • 1 <= A.length <= 100
  • 1 <= A[i].length <= 100

3.32.5 Solution - Frequency Intersection

3.32.5.1 Walkthrough

Track the frequency of each letter in the first string. For every next string, compute its frequency and take the element-wise minimum with the running counts. At the end, output each letter as many times as its remaining count.

3.32.5.2 Analysis

  • Time Complexity: O(n * L) where L is average word length
  • Space Complexity: O(1) for 26 counts

3.32.5.3 Implementation Steps

  1. Initialize minFreq with counts from the first word.
  2. For each subsequent word:
    1. Count characters into temp.
    2. Update minFreq[i] = min(minFreq[i], temp[i]).
  3. Build the result by outputting each character minFreq[i] times.

3.32.5.4 Code - Java

public List<String> commonChars(String[] A) {
    int[] minFreq = new int[26];
    Arrays.fill(minFreq, Integer.MAX_VALUE);

    for (String word : A) {
        int[] freq = new int[26];
        for (char c : word.toCharArray()) {
            freq[c - 'a']++;
        }
        for (int i = 0; i < 26; i++) {
            minFreq[i] = Math.min(minFreq[i], freq[i]);
        }
    }

    List<String> result = new ArrayList<>();
    for (int i = 0; i < 26; i++) {
        for (int count = 0; count < minFreq[i]; count++) {
            result.add(String.valueOf((char) ('a' + i)));
        }
    }

    return result;
}