Find Common Characters - Leetcode Solution

Problem Statement: 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"]

Approach: We can use a hash map to keep track of the frequency of each character in each string. We can then iterate over the hash map and find the characters that appear in all strings.

Solution:

1. Initialize a hash map. Iterate through the first string in the input array A and count the frequency of each character and store it in the hash map.
2. Iterate through the other strings in A and update the frequency of characters in the hash map. If a character is not present in any of the strings, remove that character from the hash map.
3. Create an empty list to store the common characters.
4. Iterate through the hash map and append the character to the common characters list as many times as it appears in all the strings.
5. Return the common characters list.

Java Code: class Solution { public List<String> commonChars(String[] A) { int[] freq = new int[26]; for (char c : A[0].toCharArray()) { freq[c - 'a']++; } for (int i = 1; i < A.length; i++) { int[] freqTemp = new int[26]; for (char c : A[i].toCharArray()) { freqTemp[c - 'a']++; } for (int j = 0; j < 26; j++) { freq[j] = Math.min(freq[j], freqTemp[j]); } } List<String> commonChars = new ArrayList<>(); for (int i = 0; i < 26; i++) { while (freq[i] > 0) { commonChars.add(String.valueOf((char) (i + 'a'))); freq[i]--; } } return commonChars; } }

Time Complexity: O(N*M), where N is the length of the input array and M is the length of the longest string in the array. Space Complexity: O(1) since the size of the frequency array is constant at 26.

1