# Find Common Characters
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-common-characters)
Canonical: https://scaleengineer.com/dsa/problems/find-common-characters
**Data structures:** Array, Hash Table, String
**Companies:** [Tripadvisor](https://scaleengineer.com/companies/tripadvisor)
---
## 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**.

**Example 1:**

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

**Example 2:**

**Input:** words = ["cool","lock","cook"]
**Output:** ["c","o"]

**Constraints:**

* `1 <= words.length <= 100`
* `1 <= words[i].length <= 100`
* `words[i]` consists of lowercase English letters.

# Approaches
## Brute-Force with List Manipulation
This approach uses the first word as a reference and iteratively finds the intersection of characters with each subsequent word. To correctly handle duplicate characters, it converts strings to lists of characters and removes characters from the lists as they are matched. This ensures that if a character appears `k` times in the common set, it must have appeared at least `k` times in every word.
**Time:** O(N * M^2), where N is the number of words and M is the maximum length of a word. The outer loop runs N-1 times. Inside, we iterate through the common characters list (size up to M), and for each character, we perform `contains` and `remove` operations on another list, both of which take O(M) time. This results in an O(M^2) operation for each word. · **Space:** O(M), where M is the maximum length of a word. We use several lists (`commonChars`, `currentWordChars`, `newCommonChars`) whose sizes are at most M. The result list also takes O(M) space.
**Pros:** The logic is relatively straightforward, following a direct simulation of finding an intersection.; It's easy to implement without requiring knowledge of more optimized data structures like frequency maps.
**Cons:** Highly inefficient due to repeated list traversals and removals. The `List.remove(Object)` operation has a linear time complexity, leading to a quadratic time complexity relative to word length.; Creates multiple intermediate lists, which can lead to higher memory churn and pressure on the garbage collector.
### Explanation
The algorithm begins by converting the first word into a list of characters, which serves as our initial set of potential common characters. It then iterates through the remaining words one by one. In each iteration, it compares the current set of common characters against the characters of the current word. A new list is built containing only the characters present in both. A crucial step is that whenever a character is matched and added to the new common list, it is removed from the current word's character list. This prevents the same character instance from being matched multiple times. This process of refining the common character list continues until all words have been processed. The final list contains all characters, including duplicates, that are present in every single word.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> commonChars(String[] words) {
        if (words == null || words.length == 0) {
            return new ArrayList<>();
        }

        List<Character> commonChars = new ArrayList<>();
        for (char c : words[0].toCharArray()) {
            commonChars.add(c);
        }

        for (int i = 1; i < words.length; i++) {
            List<Character> currentWordChars = new ArrayList<>();
            for (char c : words[i].toCharArray()) {
                currentWordChars.add(c);
            }

            List<Character> newCommonChars = new ArrayList<>();
            for (Character c : commonChars) {
                if (currentWordChars.contains(c)) {
                    newCommonChars.add(c);
                    currentWordChars.remove(c); // Remove one occurrence to handle duplicates
                }
            }
            commonChars = newCommonChars;
        }

        List<String> result = new ArrayList<>();
        for (Character c : commonChars) {
            result.add(String.valueOf(c));
        }
        return result;
    }
}
```
### Algorithm
- Initialize a list of characters, `commonChars`, with the characters from the first word, `words[0]`.
- Loop through the rest of the words in the `words` array, from the second word to the last.
- For each word, create a temporary list of its characters, `currentWordChars`.
- Create a new empty list, `newCommonChars`, to store the characters that are common up to this point.
- Iterate through each character `c` in the `commonChars` list.
- Check if `c` exists in `currentWordChars`.
- If it does, add `c` to `newCommonChars` and remove one instance of `c` from `currentWordChars` to ensure duplicates are handled correctly.
- After checking all characters from `commonChars`, update `commonChars` to be `newCommonChars`.
- After iterating through all the words, convert the final `commonChars` list of characters into a list of strings and return it.

## Frequency Counting with Arrays
This is a highly efficient approach that uses frequency count arrays to solve the problem. Since the input consists only of lowercase English letters, we can use an array of size 26 to track the counts of each character. The core idea is to find the minimum frequency of each character across all words. This minimum frequency represents how many times a character can appear in the final result.
**Time:** O(L), where L is the total number of characters in all words combined (sum of all word lengths). We iterate through each character of each word exactly once to build frequency maps. The update step takes a constant O(26) time for each of the N words. Thus, the total time is proportional to the total input size. · **Space:** O(1). The space used for the frequency arrays (`minFreq`, `currentFreq`) is constant (26 integers), regardless of the input size. The space for the output list is not typically counted in complexity analysis, but it would be O(M) where M is the length of the shortest word.
**Pros:** Extremely efficient in both time and space.; Scales linearly with the total number of characters, making it suitable for large inputs.; Uses fixed-size arrays, which are very fast and memory-efficient.
**Cons:** The logic might be slightly less intuitive at first glance for beginners compared to direct character comparison.
### Explanation
The algorithm is optimized by avoiding costly string and list operations. It starts by creating a frequency array, `minFreq`, representing the character counts of the first word. This array acts as our initial baseline for common characters. Then, it iterates through the remaining words. For each word, it computes a new frequency array, `currentFreq`. The crucial step is updating `minFreq` by comparing it with `currentFreq` element by element and keeping the minimum value for each character's count. For instance, if `minFreq` has a count of 3 for 'l' and `currentFreq` has a count of 2, the new `minFreq` count for 'l' becomes 2. This ensures that `minFreq` always stores the bottleneck, i.e., the minimum number of times each character has appeared so far. After processing all words, `minFreq` contains the exact counts for the final common characters. The result list is then constructed based on these final counts.

```java
import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;

class Solution {
    public List<String> commonChars(String[] words) {
        int[] minFreq = new int[26];
        // Initialize with the frequencies from the first word
        for (char c : words[0].toCharArray()) {
            minFreq[c - 'a']++;
        }

        // Iterate through the rest of the words to find the minimum frequencies
        for (int i = 1; i < words.length; i++) {
            int[] currentFreq = new int[26];
            for (char c : words[i].toCharArray()) {
                currentFreq[c - 'a']++;
            }
            // Update the global minimum frequency for each character
            for (int j = 0; j < 26; j++) {
                minFreq[j] = Math.min(minFreq[j], currentFreq[j]);
            }
        }

        // Build the result list from the final minimum frequencies
        List<String> result = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            while (minFreq[i] > 0) {
                result.add(String.valueOf((char) ('a' + i)));
                minFreq[i]--;
            }
        }
        return result;
    }
}
```
### Algorithm
- Create an integer array `minFreq` of size 26. Initialize it by counting the character frequencies of the first word, `words[0]`.
- Iterate through the rest of the words in the array (from the second word onwards).
- For each word, create a temporary frequency array `currentFreq` of size 26 and populate it with the character counts of that word.
- After processing the current word, update the `minFreq` array. For each character from 'a' to 'z' (index 0 to 25), set its count in `minFreq` to the minimum of its current count and its count in `currentFreq`. (`minFreq[j] = Math.min(minFreq[j], currentFreq[j])`).
- After iterating through all words, the `minFreq` array holds the counts of characters common to all words.
- Create a final result list. Iterate through the `minFreq` array from index 0 to 25. For each index `i`, add the corresponding character to the result list `minFreq[i]` times.
- Return the result list.

# Solutions
### Java

```java
class Solution {
public
  List<String> commonChars(String[] words) {
    int[] cnt = new int[26];
    Arrays.fill(cnt, 10000);
    for (String w : words) {
      int[] ccnt = new int[26];
      for (int i = 0; i < w.length(); ++i) {
        ++ccnt[w.charAt(i) - 'a'];
      }
      for (int i = 0; i < 26; ++i) {
        cnt[i] = Math.min(cnt[i], ccnt[i]);
      }
    }
    List<String> ans = new ArrayList<>();
    for (int i = 0; i < 26; ++i) {
      while (cnt[i]-- > 0) {
        ans.add(String.valueOf((char)(i + 'a')));
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<string> commonChars(vector<string> &words) {
    int cnt[26];
    memset(cnt, 0x3f, sizeof(cnt));
    for (auto &w : words) {
      int ccnt[26]{};
      for (char &c : w) {
        ++ccnt[c - 'a'];
      }
      for (int i = 0; i < 26; ++i) {
        cnt[i] = min(cnt[i], ccnt[i]);
      }
    }
    vector<string> ans;
    for (int i = 0; i < 26; ++i) {
      while (cnt[i]--) {
        ans.emplace_back(1, i + 'a');
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def commonChars(self, words: List[str]) -> List[str]: cnt = Counter(words[0]) for w in words: ccnt = Counter(w) for c in cnt . keys(): cnt[c] = min(cnt[c], ccnt[c]) ans = [] for c, v in cnt . items(): ans . extend([c] * v) return ans

```