Skip to content

1002. Find Common Characters

SourceWeekly Contest 126 Q1DifficultyEasyRating1279

Description

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.

Solutions

Solution 1: Counting

Thinking

Scanning every word for each letter is feasible: both the number of words and their lengths are at most \(100\). Repeatedly walking the same alphabet still wastes comparisons.

A letter appears in the answer as many times as its minimum frequency over all words — the intersection of the multisets.

We therefore count the first word, take a pointwise \(\min\) with every later word, and expand the counts. The alphabet has size \(26\), so extra space is constant.

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.

1
2
3
4
5
6
7
8
class Solution:
    def commonChars(self, words: List[str]) -> List[str]:
        cnt = Counter(words[0])
        for w in words:
            t = Counter(w)
            for c in cnt:
                cnt[c] = min(cnt[c], t[c])
        return list(cnt.elements())

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<String> commonChars(String[] words) {
        int[] cnt = new int[26];
        Arrays.fill(cnt, 20000);
        for (var w : words) {
            int[] t = new int[26];
            for (int i = 0; i < w.length(); ++i) {
                ++t[w.charAt(i) - 'a'];
            }
            for (int i = 0; i < 26; ++i) {
                cnt[i] = Math.min(cnt[i], t[i]);
            }
        }
        List<String> ans = new ArrayList<>();
        for (int i = 0; i < 26; ++i) {
            ans.addAll(Collections.nCopies(cnt[i], String.valueOf((char) ('a' + i))));
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<string> commonChars(vector<string>& words) {
        vector<int> cnt(26, 20000);
        for (const auto& w : words) {
            vector<int> t(26, 0);
            for (char c : w) {
                ++t[c - 'a'];
            }
            for (int i = 0; i < 26; ++i) {
                cnt[i] = min(cnt[i], t[i]);
            }
        }
        vector<string> ans;
        for (int i = 0; i < 26; ++i) {
            for (int j = 0; j < cnt[i]; ++j) {
                ans.push_back(string(1, 'a' + i));
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
}

Comments