1002. Find Common Characters - Solution

Q: Is Find Common Characters easy or hard?

Find Common Characters is classified as an Easy problem. The challenge mainly involves tracking minimum character frequencies across multiple strings using arrays or hash maps.

Q: Find Common Characters Python/Java solution

In Python and Java, the common solution uses either a dictionary/map or an integer array of size 26. For each word, compute character frequencies and update the global minimum counts. Finally, rebuild the result list using the stored frequencies.

Q: How to solve Find Common Characters in O(n)?

Treat each word as part of a single pass frequency comparison. Compute the character frequency for the first word, then update it with the minimum frequency from every other word. Since each character is processed once per string, the total complexity becomes O(n * k).

Q: What is the best approach for Find Common Characters?

The frequency array approach is typically the best solution. Because the problem only uses lowercase English letters, you can maintain a 26-length array and keep the minimum frequency across all strings. This results in O(n * k) time and O(26) space while avoiding hash map overhead.

Q: Is Find Common Characters asked at Google/Amazon/Meta?

Variants of character frequency and string intersection problems appear frequently in interviews at companies like Amazon, Google, and Meta. They test understanding of hash tables, counting techniques, and efficient string processing.

Q: What data structure is used in Find Common Characters?

The main data structures are hash maps or fixed-size frequency arrays. A hash map stores character counts dynamically, while a 26-length array provides faster constant-time indexing for lowercase letters.

Q: What is the time complexity of Find Common Characters?

The time complexity is O(n * k), where n is the number of words and k is the average length of each word. Each string is scanned once to count character frequencies, and only 26 characters are compared when updating the global minimum counts.

The 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.

Approach overview

Problem Overview: You are given an array of lowercase strings. The goal is to return all characters that appear in every word, including duplicates. If a character appears twice in all strings, it must appear twice in the result.

Approach 1: Counting Characters with Maps (Time: O(n * k), Space: O(26))

This approach uses a hash map to track character frequencies for each word. Start by counting characters in the first word. Then iterate through the remaining words and update the counts by taking the minimum frequency for each character. If a character appears fewer times in another word, reduce the stored count accordingly. The final map represents the characters common across all words. This approach works well when using a hash table abstraction because it keeps the logic simple and easy to reason about.

After processing all strings, iterate through the map and append each character to the result as many times as its stored frequency. The key insight is that the minimum frequency of each character across all words determines how many times it appears in the answer.

Approach 2: Utilizing Frequency Arrays Directly (Time: O(n * k), Space: O(26))

Since all characters are lowercase English letters, a fixed-size frequency array of length 26 replaces the hash map. First compute the frequency array for the first string. Then iterate through the remaining words and compute a temporary frequency array for each word. Update the global array by taking the minimum value for every index.

This method avoids hash lookups and relies on direct index access, making it slightly faster in practice. For each character position i, the stored value represents the minimum number of times that character appears in every word. After processing all strings, iterate through the array and append characters to the result accordingly.

This technique is common in problems involving arrays and string frequency counting where the character set is small and fixed. Using arrays keeps memory predictable and operations constant time.

Recommended for interviews: The frequency array approach is usually preferred. It demonstrates awareness of constraints (only 26 lowercase letters) and reduces overhead compared to hash maps. The map-based approach still shows solid understanding of frequency counting and works well if the character set were larger or unknown.

Approach 1: Approach 1: Counting Characters with Maps

In this approach, we will use a hash map (or dictionary) to store the frequency of each character for each word. We then update a common frequency count table that holds the minimum frequency of each character across all words. This ensures that only characters existing in all words are recorded.

Python

def findCommonChars(words):
    from collections import Counter
    min_count = Counter(words[0])
    for word in words[1:]:
        min_count &= Counter(word)
    return list(min_count.elements())

if __name__ == "__main__":
    words = ["bella", "label", "roller"]
    print(findCommonChars(words))

Java

import java.util.*;

public class CommonChars {
    public static List<Character> findCommonChars(String[] words) {
        int[] minCount = new int[26];
        Arrays.fill(minCount, Integer.MAX_VALUE);

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

        List<Character> result = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < minCount[i]; j++) {
                result.add((char)(i + 'a'));
            }
        }
        return result;
    }

    public static void main(String[] args) {
        String[] words = {"bella", "label", "roller"};
        List<Character> result = findCommonChars(words);
        System.out.println(result);
    }
}

C++

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

std::vector<char> findCommonChars(const std::vector<std::string>& words) {
    std::vector<int> min_count(26, INT_MAX);

    for(const auto& word : words) {
        std::vector<int> count(26, 0);
        for(char c : word) {
            count[c - 'a']++;
        }
        for(int i = 0; i < 26; i++) {
            min_count[i] = std::min(min_count[i], count[i]);
        }
    }

    std::vector<char> result;
    for(int i = 0; i < 26; i++) {
        while(min_count[i]-- > 0) {
            result.push_back(i + 'a');
        }
    }
    return result;
}

int main() {
    std::vector<std::string> words = {"bella", "label", "roller"};
    std::vector<char> result = findCommonChars(words);
    for(char c : result) {
        std::cout << c << " ";
    }
    return 0;
}

JavaScript

function findCommonChars(words) {
    let minCount = new Array(26).fill(Infinity);

    for (let word of words) {
        let count = new Array(26).fill(0);
        for (let char of word) {
            count[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
        }
        for (let i = 0; i < 26; i++) {
            minCount[i] = Math.min(minCount[i], count[i]);
        }
    }

    let result = [];
    for (let i = 0; i < 26; i++) {
        for (let j = 0; j < minCount[i]; j++) {
            result.push(String.fromCharCode(i + 'a'.charCodeAt(0)));
        }
    }
    return result;
}

let words = ['bella', 'label', 'roller'];
console.log(findCommonChars(words));

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

void findCommonChars(char** words, int wordsSize) {
    int count[wordsSize][26];
    int minCount[26];
    bool first = true;
    
    for (int i = 0; i < wordsSize; i++) {
        memset(count[i], 0, 26 * sizeof(int));
        for (int j = 0; words[i][j] != '\0'; j++) {
            count[i][words[i][j] - 'a']++;
        }
    }

    memset(minCount, 0x7f, 26 * sizeof(int)); // 0x7f is safe for int
    for (int i = 0; i < 26; i++) {
        if (!first) {
            for (int j = 0; j < wordsSize; j++) {
                if (count[j][i] < minCount[i]) {
                    minCount[i] = count[j][i];
                }
            }
        } else {
            for (int j = 0; j < wordsSize; j++) {
                minCount[i] = count[j][i] < minCount[i] ? count[j][i] : minCount[i];
            }
            first = false;
        }
    }

    for (int i = 0; i < 26; i++) {
        for (int j = 0; j < minCount[i]; j++) {
            printf("%c ", i + 'a');
        }
    }
    printf("\n");
}

int main() {
    char* words[] = {"bella", "label", "roller"};
    findCommonChars(words, 3);
    return 0;
}

using System;
using System.Collections.Generic;
using System.Linq;

public class CommonChars {
    public static IList<char> FindCommonChars(string[] words) {
        var minCount = new int[26];
        Array.Fill(minCount, int.MaxValue);

        foreach (var word in words) {
            var count = new int[26];
            foreach (var c in word) {
                count[c - 'a']++;
            }
            for (int i = 0; i < 26; i++) {
                minCount[i] = Math.Min(minCount[i], count[i]);
            }
        }

        var result = new List<char>();
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < minCount[i]; j++) {
                result.Add((char)(i + 'a'));
            }
        }
        return result;
    }

    public static void Main() {
        var words = new string[]{"bella", "label", "roller"};
        var result = FindCommonChars(words);
        Console.WriteLine(String.Join(", ", result));
    }
}

In Python, we use the Counter from the collections module to easily manage frequencies. We combine them by intersecting counts, resulting in only the minimum occurring characters across all words.

Complexity

Time Complexity: O(N*K). Space Complexity: O(1) due to fixed character counting space.

Try this approach in the editor

Approach 2: Approach 2: Utilizing Frequency Arrays Directly

We can alternatively use direct character arrays to represent frequencies and update these arrays with each subsequent word processed. Starting with the first word's character frequencies, we iteratively compute the minimum with the rest.

Python

def findCommonChars(words):
    min_count = [float('inf')] * 26

    for word in words:
        count = [0] * 26
        for char in word:
            count[ord(char) - ord('a')] += 1
        for i in range(26):
            min_count[i] = min(min_count[i], count[i])

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

if __name__ == "__main__":
    words = ["bella", "label", "roller"]
    print(findCommonChars(words))

Java

import java.util.*;

public class CommonChars {
    public static List<Character> findCommonChars(String[] words) {
        int[] minFrequency = new int[26];
        Arrays.fill(minFrequency, Integer.MAX_VALUE);

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

        List<Character> result = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            while (minFrequency[i]-- > 0) {
                result.add((char) (i + 'a'));
            }
        }
        return result;
    }

    public static void main(String[] args) {
        String[] words = new String[]{"bella", "label", "roller"};
        List<Character> result = findCommonChars(words);
        System.out.println(result);
    }
}

C++

#include <iostream>
#include <vector>
#include <string>
#include <climits>

std::vector<char> findCommonChars(const std::vector<std::string>& words) {
    std::vector<int> minFrequency(26, INT_MAX);

    for (const auto& word : words) {
        std::vector<int> freq(26, 0);
        for (const char& c : word) {
            freq[c - 'a']++;
        }
        for (int i = 0; i < 26; ++i) {
            minFrequency[i] = std::min(minFrequency[i], freq[i]);
        }
    }

    std::vector<char> result;
    for (int i = 0; i < 26; ++i) {
        for (int j = 0; j < minFrequency[i]; ++j) {
            result.push_back('a' + i);
        }
    }
    return result;
}

int main() {
    std::vector<std::string> words = {"bella", "label", "roller"};
    std::vector<char> results = findCommonChars(words);
    for (char c : results) {
        std::cout << c << " ";
    }
    std::cout << std::endl;
    return 0;
}

JavaScript

function findCommonChars(words) {
    let minFrequency = new Array(26).fill(Infinity);

    for (let word of words) {
        let frequency = new Array(26).fill(0);
        for (let char of word) {
            frequency[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
        }
        for (let i = 0; i < 26; i++) {
            minFrequency[i] = Math.min(minFrequency[i], frequency[i]);
        }
    }

    let result = [];
    for (let i = 0; i < 26; i++) {
        for (let j = 0; j < minFrequency[i]; j++) {
            result.push(String.fromCharCode(i + 'a'.charCodeAt(0)));
        }
    }
    return result;
}

let words = ['bella', 'label', 'roller'];
console.log(findCommonChars(words));

#include <stdio.h>
#include <string.h>

void findCommonChars(char** words, int wordsSize) {
    int minFrequency[26];
    memset(minFrequency, 0x7f, 26 * sizeof(int));

    for (int i = 0; i < wordsSize; i++) {
        int currentFrequency[26] = {0};

        for (int j = 0; words[i][j] != '\0'; j++) {
            currentFrequency[words[i][j] - 'a']++;
        }

        for (int k = 0; k < 26; k++) {
            if (currentFrequency[k] < minFrequency[k]) {
                minFrequency[k] = currentFrequency[k];
            }
        }
    }

    for (int i = 0; i < 26; i++) {
        for (int j = 0; j < minFrequency[i]; j++) {
            printf("%c ", i + 'a');
        }
    }
    printf("\n");
}

int main() {
    char* words[] = {"bella", "label", "roller"};
    findCommonChars(words, 3);
    return 0;
}

using System;
using System.Collections.Generic;

public class CommonChars {
    public static IList<char> FindCommonChars(string[] words) {
        int[] minFrequency = new int[26];
        Array.Fill(minFrequency, int.MaxValue);

        foreach (string word in words) {
            int[] frequency = new int[26];
            foreach (char c in word) {
                frequency[c - 'a']++;
            }
            for (int i = 0; i < 26; i++) {
                minFrequency[i] = Math.Min(minFrequency[i], frequency[i]);
            }
        }

        List<char> result = new List<char>();
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < minFrequency[i]; j++) {
                result.Add((char)(i + 'a'));
            }
        }
        return result;
    }

    public static void Main(string[] args) {
        string[] words = {"bella", "label", "roller"};
        IList<char> result = FindCommonChars(words);
        Console.WriteLine(string.Join(", ", result));
    }
}

Here, the Python implementation uses lists to maintain and update frequency counts, finding the minimum number across all word frequencies directly within the predictable character space.

Complexity

Time Complexity: O(N*K). Space Complexity: O(1).

Try this approach in the editor

Approach 3: Counting

We use an array cnt of length 26 to record the minimum number of times each character appears in all strings. Finally, we traverse the cnt array and add characters with a count greater than 0 to the answer.

The time complexity is O(n sum w_i), and the space complexity is O(|\Sigma|). Here, n is the length of the string array words, w_i is the length of the i-th string in the array words, and |\Sigma| is the size of the character set, which is 26 in this problem.

TypeScript

function commonChars(words: string[]): string[] {
    const cnt = Array(26).fill(20000);
    const aCode = 'a'.charCodeAt(0);
    for (const w of words) {
        const t = Array(26).fill(0);
        for (const c of w) {
            t[c.charCodeAt(0) - aCode]++;
        }
        for (let i = 0; i < 26; i++) {
            cnt[i] = Math.min(cnt[i], t[i]);
        }
    }
    const ans: string[] = [];
    for (let i = 0; i < 26; i++) {
        cnt[i] && ans.push(...String.fromCharCode(i + aCode).repeat(cnt[i]));
    }
    return ans;
}

func commonChars(words []string) (ans []string) {
	cnt := make([]int, 26)
	for i := range cnt {
		cnt[i] = 20000
	}
	for _, w := range words {
		t := make([]int, 26)
		for _, c := range w {
			t[c-'a']++
		}
		for i := 0; i < 26; i++ {
			cnt[i] = min(cnt[i], t[i])
		}
	}
	for i := 0; i < 26; i++ {
		for j := 0; j < cnt[i]; j++ {
			ans = append(ans, string('a'+rune(i)))
		}
	}
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Counting Characters with Maps	Time Complexity: O(N*K). Space Complexity: O(1) due to fixed character counting space.
Approach 2: Utilizing Frequency Arrays Directly	Time Complexity: O(N*K). Space Complexity: O(1).
Counting	–

Complexity analysis

Approach	Time	Space	When to Use
Counting Characters with Maps	O(n * k)	O(26)	General solution when using hash maps or when character set size may vary
Frequency Arrays Directly	O(n * k)	O(26)	Best choice when characters are limited to lowercase letters and constant-time indexing is preferred

Frequently asked questions

Is Find Common Characters easy or hard?

Find Common Characters is classified as an Easy problem. The challenge mainly involves tracking minimum character frequencies across multiple strings using arrays or hash maps.

Find Common Characters Python/Java solution

In Python and Java, the common solution uses either a dictionary/map or an integer array of size 26. For each word, compute character frequencies and update the global minimum counts. Finally, rebuild the result list using the stored frequencies.

How to solve Find Common Characters in O(n)?

Treat each word as part of a single pass frequency comparison. Compute the character frequency for the first word, then update it with the minimum frequency from every other word. Since each character is processed once per string, the total complexity becomes O(n * k).

What is the best approach for Find Common Characters?

The frequency array approach is typically the best solution. Because the problem only uses lowercase English letters, you can maintain a 26-length array and keep the minimum frequency across all strings. This results in O(n * k) time and O(26) space while avoiding hash map overhead.

Is Find Common Characters asked at Google/Amazon/Meta?

Variants of character frequency and string intersection problems appear frequently in interviews at companies like Amazon, Google, and Meta. They test understanding of hash tables, counting techniques, and efficient string processing.

What data structure is used in Find Common Characters?

The main data structures are hash maps or fixed-size frequency arrays. A hash map stores character counts dynamically, while a 26-length array provides faster constant-time indexing for lowercase letters.

What is the time complexity of Find Common Characters?

The time complexity is O(n * k), where n is the number of words and k is the average length of each word. Each string is scanned once to count character frequencies, and only 26 characters are compared when updating the global minimum counts.

Find Common Characters solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Counting Characters with Maps

Approach 2: Approach 2: Utilizing Frequency Arrays Directly

Approach 3: Counting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find Common Characters solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Counting Characters with Maps

Approach 2: Approach 2: Utilizing Frequency Arrays Directly

Approach 3: Counting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems