Problem

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.

Examples

Example 1:

1
2

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

Example 2:

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

Solution

Method 1 - Find min number of characters in all words

Here is the approach we can follow:

  1. Create commonCharCnt as common character frequency map, which is an int array of 26 characters, as we have to take care of only lower case alphabets.
  2. Now, for each word we calculate the frequency map for it say in currCharCnt array
  3. Update commonCharCnt such that commonCharCnt[i] = currCharCnt[i]
  4. Now, we return all the characters from commonCharCnt where frequency of character is not 0.

Here is the video explanation:

Code

 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

class Solution {

	public List<String> commonChars(String[] words) {
		int[] commonCharCnt = new int[26];
		Arrays.fill(commonCharCnt, Integer.MAX_VALUE);

		for (String word: words) {
			int[] currCharCnt = new int[26];
			word.chars().forEach(character -> ++currCharCnt[character - 'a']);

			for (int i = 0; i < 26; i++) {
				commonCharCnt[i] = Math.min(commonCharCnt[i], currCharCnt[i]);
			}
		}

		List<String> commonChars = new ArrayList<>(); 
		for (char character = 'a'; character <= 'z'; character++) {
			String currChar = Character.toString(character);

			while (commonCharCnt[character - 'a']--> 0) {
				commonChars.add(currChar);
			}
		}

		return commonChars;
	}
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1) (2 O(26) count arrays for common and current word.)