Find Common Characters

Updated on 26 May, 2025
Find Common Characters header image

Problem Statement

The task is to identify characters that are common in all the strings of a given array named words. Each character in the resulting array should appear as many times as it appears in the string where it is least frequent among all strings in the words array. The final result can be in any sequence and should include duplicates if a character is common in all strings but appears multiple times.

Examples

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

Approach and Intuition

To solve this problem, let's explore a systematic approach:

  1. Character Frequency Counting:

    • First, count the frequency of each character for each individual string in the input list words. This can be accomplished using a list of dictionaries, where each dictionary represents the frequency count of characters for a specific string.
  2. Common Characters Identification:

    • Using the frequency counts from the previous step, identify characters that are common to all strings. This involves comparing the dictionaries to find the minimum frequency of each character across all strings.
  3. Building the Resultant Array:

    • Once you have identified the common characters and determined their minimum frequency across all strings, populate an output array with these characters, repeated according to their minimum frequency.

Example Process:

  • For words = ["bella","label","roller"], count individual character frequencies for each word.
    • "bella": {'b': 1, 'e': 1, 'l': 2, 'a': 1}
    • "label": {'l': 2, 'a': 1, 'b': 1, 'e': 1}
    • "roller": {'r': 2, 'o': 1, 'l': 2, 'e': 1}
  • Identify common characters across all words.
    • 'e' and 'l' appear in all, with 'e' appearing at least once and 'l' at least twice in every word.
  • Construct the result array based on minimum appearances across all arrays: ['e', 'l', 'l']

By following these steps, you can effectively find the intersection of characters in various strings of the words array, including handling duplicate occurrences.

Solutions

  • C++
  • Java
  • Python
cpp
class Solution {
public:
    vector<string> findCommonCharacters(vector<string>& inputWords) {
        int countOfWords = inputWords.size();
        vector<int> freqCommon(26), freqCurrent(26);
        vector<string> output;

        // Set the frequency from the first word
        for (char& c : inputWords[0]) {
            freqCommon[c - 'a']++;
        }

        for (int wordIndex = 1; wordIndex < countOfWords; wordIndex++) {
            fill(freqCurrent.begin(), freqCurrent.end(), 0);

            // Count frequency in the current word
            for (char& c : inputWords[wordIndex]) {
                freqCurrent[c - 'a']++;
            }

            // Retain minimum frequency
            for (int idx = 0; idx < 26; idx++) {
                freqCommon[idx] = min(freqCommon[idx], freqCurrent[idx]);
            }
        }

        // Prepare result based on common frequencies
        for (int idx = 0; idx < 26; idx++) {
            for (int count = 0; count < freqCommon[idx]; count++) {
                output.push_back(string(1, idx + 'a'));
            }
        }

        return output;
    }
};

This solution involves finding common characters among a list of strings using C++ programming language. The function findCommonCharacters accepts a vector of strings inputWords and returns a vector of strings representing the common characters across all words.

Here is a breakdown of the method:

  • Initialize countOfWords to get the total number of words in inputWords.

  • Declare two frequency arrays, freqCommon and freqCurrent, initialized to store the frequency of each letter from 'a' to 'z'.

  • Initially, set the frequency of characters from the first word in inputWords to freqCommon.

  • Iterate over the remaining words in inputWords starting from the second word. For each word:

    • Fill freqCurrent with zeros to reset frequencies for the current word.
    • Count each character's frequency in the word and update freqCurrent accordingly.
    • Update freqCommon to keep only the minimum frequency for each character encountered so far across all processed words.
  • After processing all words, construct the output vector by adding each character (from 'a' to 'z') the number of times indicated by freqCommon.

  • Return the output vector, which contains the common characters sorted in alphabetical order and repeated according to their minimum frequency across all input words.

This approach ensures efficient computation of common characters by leveraging frequency arrays and minimizing the number of comparisons needed across multiple words.

java
class Solution {

    public List<String> findCommonCharacters(String[] array) {
        int numWords = array.length;
        int[] minCounts = new int[26];
        int[] charCounts = new int[26];
        List<String> commonChars = new ArrayList<>();

        for (char c : array[0].toCharArray()) {
            minCounts[c - 'a']++;
        }

        for (int i = 1; i < numWords; i++) {
            Arrays.fill(charCounts, 0);

            for (char c : array[i].toCharArray()) {
                charCounts[c - 'a']++;
            }

            for (int idx = 0; idx < 26; idx++) {
                minCounts[idx] = Math.min(minCounts[idx], charCounts[idx]);
            }
        }

        for (int idx = 0; idx < 26; idx++) {
            while (minCounts[idx] > 0) {
                commonChars.add(String.valueOf((char) (idx + 'a')));
                minCounts[idx]--;
            }
        }

        return commonChars;
    }
}

The provided Java code defines a method findCommonCharacters inside a class named Solution, which identifies common characters appearing in all the strings of an input array.

  • Start by initializing character count arrays for tracking minimum frequencies across all strings and for the current word being analyzed.
  • Process the first string from the array separately to set an initial character frequency count in minCounts.
  • For each subsequent string in the array, reset the charCounts for the string and update it based on the character frequencies of the current string.
  • For each character from a to z:
    • Update minCounts to hold the minimum frequency of each character across all processed strings so far.
  • Once all strings have been processed, construct the final list of common characters:
    • Convert each character (by its minimum count) back to string form and add it to the result list commonChars.

The method returns commonChars, which contains each common character replicated according to its minimum count across all strings in the input array. This approach ensures that only characters that appear in every single word, and as many times as they appear in the word with the lowest frequency, are included in the output.

python
class Solution:
    def findCommonCharacters(self, words: List[str]) -> List[str]:
        number_of_words = len(words)
        output = []

        # Start with the first word's character count
        character_count = collections.Counter(words[0])

        for index in range(1, number_of_words):
            # Get character count for each subsequent word
            current_count = collections.Counter(words[index])

            # Intersect counts to find common minimums
            for char in character_count.keys():
                character_count[char] = min(character_count[char], current_count[char])

        # Form result list based on character frequencies
        for char, num in character_count.items():
            for _ in range(num):
                output.append(char)

        return output

The provided Python solution tackles the problem of finding the common characters among an array of strings. Follow these instructions to understand how the solution operates:

  1. First, determine the number of words provided in the list.
  2. Initialize an empty list to gather the final common characters.
  3. Utilize Python's collections.Counter to count the frequency of each character in the first word. This serves as the base for comparison with other words.
  4. Iterate over the remaining words starting from the second word. For each word, calculate the character frequency using collections.Counter.
  5. For each character in the pre-established character count (from the first word), update its count to the minimum frequency found between the current word and what has been tracked so far.
  6. After identifying the minimum common frequencies of characters across all words, convert these frequencies back into character form, appending each character to the output list based on its frequency.

This approach efficiently determines the shared characters by comparing and updating counts, ensuring that only truly common characters (present in all strings with the minimum frequency) are included in the final output.

Comments

No comments yet.