# 1002. Find Common Characters

LeetCode Problem Link (opens new window)

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] consist of lowercase English letters.

# Approach

The problem statement is somewhat tricky at first, but it essentially asks for characters that appear in every string within the array, including duplicate occurrences.

For instance:

Input: ["ll","ll","ll"]
Output: ["l","l"]

Upon first glance, this problem appears to be tailor-made for a hash map approach. Keywords such as "lowercase character" and "frequency" clearly suggest the use of a hash map.

One might first consider a brute force solution, processing one string at a time, leading to a time complexity of (O(n^m)), where (n) is the length of the string and (m) is the number of strings.

Clearly, this is an exponential time complexity, which is quite high. Furthermore, the code implementation isn't straightforward due to the need to handle duplicate characters and replacements accordingly.

Thus, it's preferable to use a hash map approach. If you're unfamiliar with hash maps, you can refer to this article: Hash Table Basics (opens new window).

If you are not familiar with using arrays as hash maps, please check out this article: 0242.Valid Anagram (opens new window).

Once you're familiar with hash maps and their usage in arrays, we can proceed to the solution strategy.

The overall strategy is to count the frequency of each of the 26 characters in every word and then take the minimum frequency of each character. Finally, convert these into the required output format.

For illustration:

First, count the occurrence of every character in the first string. The code is as follows:

int hash[26] = {0}; // Used to count the minimal frequency of characters across all strings
for (int i = 0; i < A[0].size(); i++) { // Initialize hash using the first string
    hash[A[0][i] - 'a']++;
}

1
2
3
4

Next, count the frequency of characters in the remaining strings in hashOtherStr.

Then, take the minimum value between hash and hashOtherStr. This is the key step—taking the minimum here represents a character's minimum occurrence across all strings.

Here's the code:

int hashOtherStr[26] = {0}; // Count the frequency of characters in strings, excluding the first
for (int i = 1; i < A.size(); i++) {
    memset(hashOtherStr, 0, 26 * sizeof(int));
    for (int j = 0; j < A[i].size(); j++) {
        hashOtherStr[A[i][j] - 'a']++;
    }
    // This is crucial
    for (int k = 0; k < 26; k++) { // Update hash to keep the minimum count across strings for 26 characters
        hash[k] = min(hash[k], hashOtherStr[k]);
    }
}

1
2
3
4
5
6
7
8
9
10
11

At this point, hash contains the minimum frequency for any character that appears in all strings. Now, convert hash into the desired output format.

Here's the code:

// Convert the character counts in hash to the output format
for (int i = 0; i < 26; i++) {
    while (hash[i] != 0) { // Note the use of 'while' for multiple repeated characters
        string s(1, i + 'a'); // Convert char to string
        result.push_back(s);
        hash[i]--;
    }
}

1
2
3
4
5
6
7
8

The complete C++ code:

class Solution {
public:
    vector<string> commonChars(vector<string>& A) {
        vector<string> result;
        if (A.size() == 0) return result;
        int hash[26] = {0}; // Used to count the minimal frequency of characters across all strings
        for (int i = 0; i < A[0].size(); i++) { // Initialize hash using the first string
            hash[A[0][i] - 'a']++;
        }

        int hashOtherStr[26] = {0}; // Count the frequency of characters in strings, excluding the first
        for (int i = 1; i < A.size(); i++) {
            memset(hashOtherStr, 0, 26 * sizeof(int));
            for (int j = 0; j < A[i].size(); j++) {
                hashOtherStr[A[i][j] - 'a']++;
            }
            // Update hash to keep the minimum count across strings for 26 characters
            for (int k = 0; k < 26; k++) {
                hash[k] = min(hash[k], hashOtherStr[k]);
            }
        }
        // Convert the character counts in hash to the output format
        for (int i = 0; i < 26; i++) {
            while (hash[i] != 0) { // Note the use of 'while' for multiple repeated characters
                string s(1, i + 'a'); // Convert char to string
                result.push_back(s);
                hash[i]--;
            }
        }

        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# Other Language Versions

# Java:

class Solution {
    public List<String> commonChars(String[] A) {
        List<String> result = new ArrayList<>();
        if (A.length == 0) return result;
        int[] hash= new int[26]; // Used to count the minimal frequency of characters across all strings
        for (int i = 0; i < A[0].length(); i++) { // Initialize hash using the first string
            hash[A[0].charAt(i)- 'a']++;
        }
        // Count the frequency of characters in strings, excluding the first
        for (int i = 1; i < A.length; i++) {
            int[] hashOtherStr= new int[26];
            for (int j = 0; j < A[i].length(); j++) {
                hashOtherStr[A[i].charAt(j)- 'a']++;
            }
            // Update hash to keep the minimum count across strings for 26 characters
            for (int k = 0; k < 26; k++) {
                hash[k] = Math.min(hash[k], hashOtherStr[k]);
            }
        }
        // Convert the character counts in hash to the output format
        for (int i = 0; i < 26; i++) {
            while (hash[i] != 0) { // Note the use of 'while' for multiple repeated characters
                char c= (char) (i+'a');
                result.add(String.valueOf(c));
                hash[i]--;
            }
        }
        return result;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# Python

class Solution:
    def commonChars(self, words: List[str]) -> List[str]:
        if not words: return []
        result = []
        hash = [0] * 26 # Used to count the minimal frequency of characters across all strings
        for i, c in enumerate(words[0]):  # Initialize hash using the first string
            hash[ord(c) - ord('a')] += 1
        # Count the frequency of characters in strings, excluding the first
        for i in range(1, len(words)):
            hashOtherStr = [0] * 26
            for j in range(len(words[i])):
                hashOtherStr[ord(words[i][j]) - ord('a')] += 1
            # Update hash to keep the minimum count across strings for 26 characters
            for k in range(26):
                hash[k] = min(hash[k], hashOtherStr[k])
        # Convert the character counts in hash to the output format
        for i in range(26):
            while hash[i] != 0: # Note the use of 'while' for multiple repeated characters
                result.extend(chr(i + ord('a')))
                hash[i] -= 1
        return result

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Python 3 using collections.Counter:

class Solution:
    def commonChars(self, words: List[str]) -> List[str]:
        tmp = collections.Counter(words[0])
        l = []
        for i in range(1,len(words)):
            # Use & to take intersection
            tmp = tmp & collections.Counter(words[i])

        # The remaining keys and values are the characters and their counts that appear in every word
        for j in tmp:
            v = tmp[j]
            while(v):
                l.append(j)
                v -= 1
        return l

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# JavaScript

var commonChars = function (words) {
	let res = []
	let size = 26
	let firstHash = new Array(size).fill(0)   // Initialize hash array

	let a = "a".charCodeAt()
	let firstWord = words[0]
	for (let i = 0; i < firstWord.length; i++) { // Count first word
		let idx = firstWord[i].charCodeAt()
		firstHash[idx - a] += 1
	}
	
	let otherHash = new Array(size).fill(0)    // Initialize other hash array
	for (let i = 1; i < words.length; i++) { // Count words 1 to n
		for (let j = 0; j < words[i].length; j++) {
			let idx = words[i][j].charCodeAt()
			otherHash[idx - a] += 1
		}
		
		for (let i = 0; i < size; i++) {
			firstHash[i] = Math.min(firstHash[i], otherHash[i])
		}
		otherHash.fill(0)
	}
	
	for (let i = 0; i < size; i++) {
		while (firstHash[i] > 0) {
			res.push(String.fromCharCode(i + a))
			firstHash[i]--
		}
	}
	return res
};

// Method 2: Using map()
var commonChars = function(words) {
  let min_count = new Map()
  // Count the minimal frequency of characters by initializing map with first string
  for(let str of words[0]) {
    min_count.set(str, ((min_count.get(str) || 0) + 1))
  }
  // Count the frequency of characters in strings from the second string
  for(let i = 1; i < words.length; i++) {
    let char_count = new Map()
    for(let str of words[i]) { // Traverse characters
      char_count.set(str, (char_count.get(str) || 0) + 1)
    }
    // Determine the minimal character count
    for(let value of min_count) { // Important to traverse min_count! Not the word
      min_count.set(value[0], Math.min((min_count.get(value[0]) || 0), (char_count.get(value[0]) || 0)))
    }
  }
  // Traverse map
  let res = []
  min_count.forEach((value, key) => {
    if(value) {
      for(let i=0; i<value; i++) {
        res.push(key)
      }
    }
  })
  return res
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

# TypeScript

  console.time("test")
  let str: string = ""
  // Create a map dictionary with letters
  let map = new Map<string, number>()
  // Initialize all map to 0
  let wordInitial: [string, number][] = words[0]
    .split("")
    .map((item) => [item, 0])
  // If there is a duplicate letter, increment its count
  for (let word of words[0]) {
    map.set(word, map.has(word) ? map.get(word) + 1 : 1)
  }
  for (let i = 1; i < words.length; i++) {
    const mapWord = new Map<string, number>(wordInitial)
    for (let j = 0; j < words[i].length; j++) {
      if (!map.has(words[i][j])) continue
      // The count of letters in mapWord should not exceed the current count in map
      if (map.get(words[i][j]) > mapWord.get(words[i][j])) {
        mapWord.set(
          words[i][j],
          mapWord.has(words[i][j]) ? mapWord!.get(words[i][j]) + 1 : 1
        )
      }
    }
    // Reinitialize map each time
    map = mapWord
  }
  for (let [key, value] of map) {
    str += key.repeat(value)
  }
  console.timeEnd("test")
  return str.split("")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

# GO

func commonChars(A []string) []string {
	var result []string
	if len(A) == 0 {
		return result
	}

	hash := make([]int, 26)  // Used to count the minimal frequency of characters across all strings
	for _, c := range A[0] { // Initialize hash using the first string
		hash[c-'a']++
	}

	for i := 1; i < len(A); i++ {
		hashOtherStr := make([]int, 26) // Count the frequency of characters in strings, excluding the first
		for _, c := range A[i] {
			hashOtherStr[c-'a']++
		}
		// Update hash to keep the minimum count across strings for 26 characters
		for k := 0; k < 26; k++ {
			hash[k] = min(hash[k], hashOtherStr[k])
		}
	}

	// Convert the character counts in hash to the output format
	for i := 0; i < 26; i++ {
		for hash[i] > 0 {
			s := string('a' + i) // Convert rune to string
			result = append(result, s)
			hash[i]--
		}
	}

	return result
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

# Swift:

func commonChars(_ words: [String]) -> [String] {
    var res = [String]()
    if words.count < 1 {
        return res
    }
    let aUnicodeScalarValue = "a".unicodeScalars.first!.value
    let lettersMaxCount = 26
    // Used to count the minimal frequency of characters across all strings
    var hash = Array(repeating: 0, count: lettersMaxCount)
    // Count the occurrence of each character in the first string
    for unicodeScalar in words.first!.unicodeScalars {
        hash[Int(unicodeScalar.value - aUnicodeScalarValue)] += 1
    }
    // Count the frequency of characters in the other strings
    for idx in 1 ..< words.count {
        var hashOtherStr = Array(repeating: 0, count: lettersMaxCount)
        for unicodeScalar in words[idx].unicodeScalars {
            hashOtherStr[Int(unicodeScalar.value - aUnicodeScalarValue)] += 1
        }
        // Update hash to keep the minimum count across strings for 26 characters
        for k in 0 ..< lettersMaxCount {
            hash[k] = min(hash[k], hashOtherStr[k])
        }
    }
    -- Convert the character counts in hash to the output format
    for i in 0 ..< lettersMaxCount {
        while hash[i] != 0 { // Note the use of 'while' for multiple repeated characters
            let currentUnicodeScalarValue: UInt32 = UInt32(i) + aUnicodeScalarValue
            let currentUnicodeScalar: UnicodeScalar = UnicodeScalar(currentUnicodeScalarValue)!
            let outputStr = String(currentUnicodeScalar) // Convert UnicodeScalar to String
            res.append(outputStr)
            hash[i] -= 1
        }
    }
    return res
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

# C:

// If two hash tables are defined as char arrays, the efficiency of both time and space can be improved
void updateHashTable(int* hashTableOne, int* hashTableTwo) {
    int i;
    for(i = 0; i < 26; i++) {
        hashTableOne[i] = hashTableOne[i] < hashTableTwo[i] ? hashTableOne[i] : hashTableTwo[i];
    }
}

char ** commonChars(char ** words, int wordsSize, int* returnSize){
    // To count the minimal frequency of characters across all strings
    int hashTable[26] = { 0 };
    // Initialize the returned char** array and its length
    *returnSize = 0;
    char** ret = (char**)malloc(sizeof(char*) * 100);

    // Return NULL if input array length is 0
    if(!wordsSize) 
        return NULL;

    int i;
    // Update the letter frequency of the first word
    for(i = 0; i < strlen(words[0]); i++)
        hashTable[words[0][i] - 'a']++;
    // Update the letter frequency of words from the second word
    for(i = 1; i < wordsSize; i++) {
        // Create a new hash table to record a new word's letter frequency
        int newHashTable[26] = { 0 };
        int j;
        for(j = 0; j < strlen(words[i]); j++) {
            newHashTable[words[i][j] - 'a']++;
        }
        // Update the original hash table
        updateHashTable(hashTable, newHashTable);
    }

    // Convert the character counts in the hash table to strings and put them into ret
    for(i = 0; i < 26; i++) {
        if(hashTable[i]) {
            int j;
            for(j = 0; j < hashTable[i]; j++) {
                char* tempString = (char*)malloc(sizeof(char) * 2);
                tempString[0] = i + 'a';
                tempString[1] = '\0';
                ret[(*returnSize)++] = tempString;
            }
        }
    }
    return ret;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

# Scala:

object Solution {
  def commonChars(words: Array[String]): List[String] = {
    // Declare the immutable List collection for the result, and declare 'res' as var since it will be reassigned
    var res = List[String]()
    var hash = new Array[Int](26) // Count the minimal frequency of characters across all strings
    // Count the occurrence of each character in the first word
    for (i <- 0 until words(0).length) {
      hash(words(0)(i) - 'a') += 1
    }
    // Count the occurrence of characters in the other words
    for (i <- 1 until words.length) {
      // Count the frequency in each of the remaining words
      var hashOtherStr = new Array[Int](26)
      for (j <- 0 until words(i).length) {
        hashOtherStr(words(i)(j) - 'a') += 1
      }
      // Update hash to ensure it contains the minimal frequency across words
      for (k <- 0 until 26) {
        hash(k) = math.min(hash(k), hashOtherStr(k))
      }
    }
    // Convert the character count in hash to the output format
    for (i <- 0 until 26) {
      for (j <- 0 until hash(i)) {
        res = res :+ (i + 'a').toChar.toString
      }
    }
    res
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# Rust:

impl Solution {
    pub fn common_chars(words: Vec<String>) -> Vec<String> {
        if words.is_empty() {
            return vec![];
        }
        let mut res = vec![];
        let mut hash = vec![0; 26];
        for i in words[0].bytes() {
            hash[(i - b'a') as usize] += 1;
        }
        for i in words.iter().skip(1) {
            let mut other_hash_str = vec![0; 26];
            for j in i.bytes() {
                other_hash_str[(j - b'a') as usize] += 1;
            }
            for k in 0..26 {
                hash[k] = hash[k].min(other_hash_str[k]);
            }
        }

        for (i, v) in hash.iter_mut().enumerate() {
            while *v > 0 {
                res.push(((i as u8 + b'a') as char).to_string());
                *v -= 1;
            }
        }

        res
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

Ruby:

def common_chars(words)
  result = []
  # Count the minimal frequency of characters across all strings
  hash = {}
  # Initialize flag
  is_first = true

  words.each do |word|
    # Record common characters
    chars = []
    word.split('').each do |chr|
      # Initialize the first string
      if is_first
        chars << chr
      else
        # Minimal previous occurrence of the letter
        if hash[chr] != nil && hash[chr] > 0
          hash[chr] -= 1
          chars << chr
        end
      end
    end

    is_first = false
    # Clear the hash, update the minimal frequency of characters
    hash.clear
    chars.each do |chr|
      if hash[chr] != nil
        hash[chr] += 1
      else
        hash[chr] = 1
      end
    end
  end

  # Convert the hash of the minimal frequency into a character array
  hash.keys.each do |key|
    for i in 0..hash[key] - 1
      result << key
    end
  end

  return result
end

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44