Maintain the minimum frequency for each letter across all words, then emit every letter that many times.
Complexity
O(total characters) time and O(1) auxiliary space for 26 counters.
Return every character shared by all words, preserving multiplicity.
Maintain the minimum frequency for each letter across all words, then emit every letter that many times.
O(total characters) time and O(1) auxiliary space for 26 counters.
package main
func commonChars(words []string) []string {
common := [26]int{}
for index := range common {
common[index] = 101
}
for _, word := range words {
count := [26]int{}
for _, character := range word {
count[character-'a']++
}
for index := range common {
if count[index] < common[index] {
common[index] = count[index]
}
}
}
result := []string{}
for index, count := range common {
for used := 0; used < count; used++ {
result = append(result, string(rune('a'+index)))
}
}
return result
}
from collections import Counter
class Solution:
def commonChars(self, words: list[str]) -> list[str]:
common = Counter(words[0])
for word in words[1:]: common &= Counter(word)
return list(common.elements())
function commonChars(words: string[]): string[] {
const common = new Array<number>(26).fill(Number.POSITIVE_INFINITY);
for (const word of words) { const count = new Array<number>(26).fill(0); for (const character of word) count[character.charCodeAt(0) - 97] += 1; for (let index = 0; index < 26; index += 1) common[index] = Math.min(common[index], count[index]); }
const result: string[] = []; common.forEach((count, index) => { for (let used = 0; used < count; used += 1) result.push(String.fromCharCode(97 + index)); }); return result;
}