Find Common Characters

• Initialize a list of characters, commonChars, with the characters from the first word, words[0].
• Loop through the rest of the words in the words array, from the second word to the last.
• For each word, create a temporary list of its characters, currentWordChars.
• Create a new empty list, newCommonChars, to store the characters that are common up to this point.
• Iterate through each character c in the commonChars list.
• Check if c exists in currentWordChars.
• If it does, add c to newCommonChars and remove one instance of c from currentWordChars to ensure duplicates are handled correctly.
• After checking all characters from commonChars, update commonChars to be newCommonChars.
• After iterating through all the words, convert the final commonChars list of characters into a list of strings and return it.

The algorithm begins by converting the first word into a list of characters, which serves as our initial set of potential common characters. It then iterates through the remaining words one by one. In each iteration, it compares the current set of common characters against the characters of the current word. A new list is built containing only the characters present in both. A crucial step is that whenever a character is matched and added to the new common list, it is removed from the current word's character list. This prevents the same character instance from being matched multiple times. This process of refining the common character list continues until all words have been processed. The final list contains all characters, including duplicates, that are present in every single word.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public List<String> commonChars(String[] words) {6        if (words == null || words.length == 0) {7            return new ArrayList<>();8        }9 10        List<Character> commonChars = new ArrayList<>();11        for (char c : words[0].toCharArray()) {12            commonChars.add(c);13        }14 15        for (int i = 1; i < words.length; i++) {16            List<Character> currentWordChars = new ArrayList<>();17            for (char c : words[i].toCharArray()) {18                currentWordChars.add(c);19            }20 21            List<Character> newCommonChars = new ArrayList<>();22            for (Character c : commonChars) {23                if (currentWordChars.contains(c)) {24                    newCommonChars.add(c);25                    currentWordChars.remove(c); // Remove one occurrence to handle duplicates26                }27            }28            commonChars = newCommonChars;29        }30 31        List<String> result = new ArrayList<>();32        for (Character c : commonChars) {33            result.add(String.valueOf(c));34        }35        return result;36    }37}

• Create an integer array minFreq of size 26. Initialize it by counting the character frequencies of the first word, words[0].
• Iterate through the rest of the words in the array (from the second word onwards).
• For each word, create a temporary frequency array currentFreq of size 26 and populate it with the character counts of that word.
• After processing the current word, update the minFreq array. For each character from 'a' to 'z' (index 0 to 25), set its count in minFreq to the minimum of its current count and its count in currentFreq. (minFreq[j] = Math.min(minFreq[j], currentFreq[j])).
• After iterating through all words, the minFreq array holds the counts of characters common to all words.
• Create a final result list. Iterate through the minFreq array from index 0 to 25. For each index i, add the corresponding character to the result list minFreq[i] times.
• Return the result list.

The algorithm is optimized by avoiding costly string and list operations. It starts by creating a frequency array, minFreq, representing the character counts of the first word. This array acts as our initial baseline for common characters. Then, it iterates through the remaining words. For each word, it computes a new frequency array, currentFreq. The crucial step is updating minFreq by comparing it with currentFreq element by element and keeping the minimum value for each character's count. For instance, if minFreq has a count of 3 for 'l' and currentFreq has a count of 2, the new minFreq count for 'l' becomes 2. This ensures that minFreq always stores the bottleneck, i.e., the minimum number of times each character has appeared so far. After processing all words, minFreq contains the exact counts for the final common characters. The result list is then constructed based on these final counts.

1import java.util.ArrayList;2import java.util.List;3import java.util.Arrays;4 5class Solution {6    public List<String> commonChars(String[] words) {7        int[] minFreq = new int[26];8        // Initialize with the frequencies from the first word9        for (char c : words[0].toCharArray()) {10            minFreq[c - 'a']++;11        }12 13        // Iterate through the rest of the words to find the minimum frequencies14        for (int i = 1; i < words.length; i++) {15            int[] currentFreq = new int[26];16            for (char c : words[i].toCharArray()) {17                currentFreq[c - 'a']++;18            }19            // Update the global minimum frequency for each character20            for (int j = 0; j < 26; j++) {21                minFreq[j] = Math.min(minFreq[j], currentFreq[j]);22            }23        }24 25        // Build the result list from the final minimum frequencies26        List<String> result = new ArrayList<>();27        for (int i = 0; i < 26; i++) {28            while (minFreq[i] > 0) {29                result.add(String.valueOf((char) ('a' + i)));30                minFreq[i]--;31            }32        }33        return result;34    }35}