Find Common Characters Leetcode Solution

Problem Statement

In this problem, we are given an array of strings. We need to print a list of all characters that appear in every string in the array(duplicates included). That is if a character appears 2 times in every string, but not 3 times, we need to have it 2 times in the result.

Note that every character in the string is a lower-case English letter and the strings have a maximum length of 100.

Example

String_Array = {"bella" , "ciao" , "espanol"}

a

String_Array = {"qweerty" , "weerty" , "eerty"}

e e r t y

Approach(HashMaps)

We can first use a hashmap, say finalCount to store the counts of characters ranging in [‘a’, ‘z’] to store their minimum common presence in all the strings. For example, if we find there are 2 ‘e’s in every string in the array, we maintain its count as 2. In order to achieve this, we visit through every string in the array and minimize the finalCount for every character in [‘a’, ‘z’]. Finally, we push a character according to its final count in a result array/list and return it.

Algorithm

1. Initialize a hash map finalCount to store the minimum common appearance of every character
2. For every lower-case English letters:
   • Set their finalCount as 100.
3. For every string word in the given array:
   • Store the count of every character in a hash map count
   • For every lower-case English letter c:
     • Set: finalCount[c] = min (finalCount[c] , count[c])
4. Initialize a list/array result to store the array of common characters.
5. For every character c in the range [‘a’, ‘z’]:
   • Add it to the list as many times as finalCount[c]
6. Print the result

Implementation of Find Common Characters Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

vector <string> commonChars(vector <string> A)
{
    unordered_map <char , int> finalCount;

    for(char c = 'a' ; c <= 'z' ; ++c)
        finalCount[c] = 100;

    unordered_map <char , int> count;

    for(string &word : A)
    {
        count.clear();
        for(char c : word)
            count[c]++;

        for(char c = 'a' ; c <= 'z' ; ++c)
            finalCount[c] = min(finalCount[c] , count[c]);
    }

    vector <string> result;

    string temp;

    int times;
    for(char c = 'a' ; c <= 'z' ; ++c)
    {
        times = finalCount[c];
        temp = c;
        while(times > 0)
        {
            result.push_back(temp);
            --times;
        }
    }
    return result;
}

int main()
{
    vector <string> A = {"qweerty" , "weerty" , "eerty"};
    vector <string> result = commonChars(A);
    if(result.empty())
        cout << "No common characters\n";
    else
    {
        for(string &s : result)
            cout << s << " ";
    }

    return 0;
}

Java Program

import java.util.*;
import java.lang.*;

class common_chars
{
    public static void main(String args[])
    {
        String[] A = {"qweerty" , "weerty" , "eerty"};
        List <String> result = commonChars(A);
        if(result.size() == 0)
            System.out.println("No common characters");
        else
        {
            for(String s : result)
                System.out.print(s + " ");
        }
    }

    static List <String> commonChars(String[] A)
    {
        HashMap <Character , Integer> finalCount = new HashMap<>();

        for(char c = 'a' ; c <= 'z' ; ++c)
            finalCount.put(c , 100);

        HashMap <Character , Integer> count = new HashMap<>();
        for(String word : A)
        {
            count.clear();
            for(char c : word.toCharArray())
                count.put(c , count.getOrDefault(c , 0) + 1);

            for(char c = 'a' ; c <= 'z' ; ++c)
                finalCount.put(c , Math.min(finalCount.get(c) , count.getOrDefault(c , 0)));
        }

        List <String> result = new ArrayList<>();

        int times;
        for(char c = 'a' ; c <= 'z' ; ++c)
        {
            times = finalCount.get(c);
            while(times > 0)
            {
                result.add(Character.toString(c));
                --times;
            }
        }
        return result;
    }
}

e e r t y

Complexity Analysis of Find Common Characters Leetcode Solution

Time Complexity

O(N) as we do a single pass of every string in the array to update the counts of characters. N = Sum of lengths of strings in the array.

Space Complexity

O(1) as we use constant memory space to store counts of characters.