Find Common Characters

Easy
594.

Find Common Characters

Find Common Characters is an easy coding problem on arrays, strings and hash table, asked in Amazon and Adobe interviews.

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 <= 100
  • 1 <= words[i].length <= 100
  • words[i] consists of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} words
 * @return {string[]}
 */
var commonChars = function(words) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 100
  • 1 <= words[i].length <= 100
  • words[i] consists of lowercase English letters.

Hints for Find Common Characters

  1. Hint 1

    For each letter, the answer's count is the minimum count across all words.

  2. Hint 2

    Count each word into a 26-slot array and fold with min.

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

  1. Initialise a 26-slot minCount to infinity.
  2. Count each word's letters and fold the result into minCount with min.
  3. 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 l in the first example.
  • Seeding minCount with 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 out

Java

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.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings