Skip to content

1002. Find Common Characters 👍

  • Time: $O(\Sigma |\texttt{words[i]}|)$
  • Space: $O(\max(|\texttt{words[i]}|))$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  vector<string> commonChars(vector<string>& words) {
    vector<string> ans;
    vector<int> commonCount(26, INT_MAX);

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

    for (char c = 'a'; c <= 'z'; ++c)
      for (int i = 0; i < commonCount[c - 'a']; ++i)
        ans.push_back(string(1, c));

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public List<String> commonChars(String[] words) {
    List<String> ans = new ArrayList<>();
    int[] commonCount = new int[26];
    Arrays.fill(commonCount, Integer.MAX_VALUE);

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

    for (char c = 'a'; c <= 'z'; ++c)
      for (int i = 0; i < commonCount[c - 'a']; ++i)
        ans.add(String.valueOf(c));

    return ans;
  }
}

1
2
3
4
class Solution:
  def commonChars(self, words: list[str]) -> list[str]:
    return functools.reduce(lambda a, b: a & b,
                            map(collections.Counter, words)).elements()