Find Common Characters — Solution in Python, Java & C++
Find Common Characters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Find Common Characters is an easy coding problem on arrays, strings and hash table, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Strings, Hash Table
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an array of strings words, return every character that appears in all of them, including duplicates.
A character appearing twice in every word appears twice in the answer. Return the characters in alphabetical order, each as a one-character string.
Example 1
Input: words = ["bella","label","roller"]
Output: ["e","l","l"]
Explanation: Every word has one e and at least two l's.
Example 2
Input: words = ["cool","lock","cook"]
Output: ["c","o"]
Example 3
Input: words = ["abc"]
Output: ["a","b","c"]
Constraints
1 <= words.length <= 1001 <= words[i].length <= 100words[i] consists of lowercase English letters.
Hints for Find Common Characters
Hint 1
For each letter, the answer's count is the minimum count across all words.
Hint 2
Count each word into a 26-slot array and fold with
min.Hint 3
Emit each letter that many times, walking a to z for the required order.
How to solve Find Common Characters
Multiset intersection: a character survives as many times as the fewest copies any single word has.
Approach
- Initialise a 26-slot
minCountto infinity. - Count each word's letters and fold the result into
minCountwithmin. - Walk the alphabet, emitting each letter
minCount[letter]times.
Why it works
A character can be taken from every word only as many times as the most constrained word allows, which is exactly the minimum of the per-word counts. Walking a-to-z produces the required alphabetical output.
Complexity
- Time —
O(total characters) - Space —
O(1) — 26 counters
Pitfalls
- Using a set of characters loses the duplicates and drops the second
lin the first example. - Seeding
minCountwith zeros makes every answer empty. - Emitting in word order rather than alphabetical order fails the exact judge.
Reference solution
Python
from typing import List
def commonChars(words: List[str]) -> List[str]:
min_count = [1000] * 26
for w in words:
c = [0] * 26
for ch in w:
c[ord(ch) - 97] += 1
for i in range(26):
if c[i] < min_count[i]:
min_count[i] = c[i]
out = []
for i in range(26):
out.extend([chr(97 + i)] * min_count[i])
return outJava
public static String[] commonChars(String[] words) {
int[] minCount = new int[26];
Arrays.fill(minCount, 1000);
for (String w : words) {
int[] c = new int[26];
for (int i = 0; i < w.length(); i++) c[w.charAt(i) - 'a']++;
for (int i = 0; i < 26; i++) minCount[i] = Math.min(minCount[i], c[i]);
}
ArrayList<String> out = new ArrayList<>();
for (int i = 0; i < 26; i++) {
for (int k = 0; k < minCount[i]; k++) out.add(String.valueOf((char) ('a' + i)));
}
return out.toArray(new String[0]);
}C++
vector<string> commonChars(vector<string>& words) {
vector<int> minCount(26, 1000);
for (auto& w : words) {
vector<int> c(26, 0);
for (char ch : w) c[ch - 'a']++;
for (int i = 0; i < 26; i++) minCount[i] = min(minCount[i], c[i]);
}
vector<string> out;
for (int i = 0; i < 26; i++) {
for (int k = 0; k < minCount[i]; k++) out.push_back(string(1, (char) ('a' + i)));
}
return out;
}JavaScript
var commonChars = function(words) {
const minCount = new Array(26).fill(1000);
for (let w = 0; w < words.length; w++) {
const c = new Array(26).fill(0);
for (let i = 0; i < words[w].length; i++) c[words[w].charCodeAt(i) - 97]++;
for (let i = 0; i < 26; i++) {
if (c[i] < minCount[i]) minCount[i] = c[i];
}
}
const out = [];
for (let i = 0; i < 26; i++) {
for (let k = 0; k < minCount[i]; k++) out.push(String.fromCharCode(97 + i));
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.