1002. Find Common Characters #

Problem #

Given an array A of strings made only from lowercase letters, return a list of all characters that show up in all strings within the list (including duplicates). For example, if a character occurs 3 times in all strings but not 4 times, you need to include that character three times in the final answer.

You may return the answer in any order.

Example 1:

Input: ["bella","label","roller"]
Output: ["e","l","l"]

Example 2:

Input: ["cool","lock","cook"]
Output: ["c","o"]

Note:

1. 1 <= A.length <= 100
2. 1 <= A[i].length <= 100
3. A[i][j] is a lowercase letter

Problem Summary #

Given a string array A consisting only of lowercase letters, return a list composed of all characters that appear in every string in the list (including duplicate characters). For example, if a character appears 3 times in every string but not 4 times, you need to include that character 3 times in the final answer. You may return the answer in any order.

Solution Approach #

• Simple problem. Given a string array A, the task is to find the characters contained in every string in this array. If a character appears multiple times, it also needs to appear multiple times in the final result. This problem can use a map to count the frequency of each string, but using an array for counting is faster. The problem states that there are only lowercase letters, so two arrays of length 26 can be used for counting. While traversing the string array, continuously reduce the frequency of each character appearing in each string (because we need to find the common characters of all strings, and the common frequency must be the minimum frequency). After obtaining the final frequency array of common characters, output them in order.

Code #

package leetcode

import "math"

func commonChars(A []string) []string {
	cnt := [26]int{}
	for i := range cnt {
		cnt[i] = math.MaxUint16
	}
	cntInWord := [26]int{}
	for _, word := range A {
		for _, char := range []byte(word) { // compiler trick - here we will not allocate new memory
			cntInWord[char-'a']++
		}
		for i := 0; i < 26; i++ {
			// Reduce the frequency so that the counted common frequency is more accurate
			if cntInWord[i] < cnt[i] {
				cnt[i] = cntInWord[i]
			}
		}
		// Reset the state
		for i := range cntInWord {
			cntInWord[i] = 0
		}
	}
	result := make([]string, 0)
	for i := 0; i < 26; i++ {
		for j := 0; j < cnt[i]; j++ {
			result = append(result, string(i+'a'))
		}
	}
	return result
}