Find the number of letters common in given set of strings

 

Introduction

Find the number of letters common in a given set of strings. (Coutesy: HackerRank) Note that the given set of strings might have duplicates.

From the problem statement, i found that since duplicates are there we should remove them and then take the whole set of strings to process the common letters.

Approach

The given input set is as follows: N is the given number of strings, example, case 3

3
aaaabbc
hdjnffb
ccgdaab

Output:

1

The count of common characters across the above 3 strings is only ‘b’

Steps:

• Remove the duplicate in each string to get a unique string
• Process the whole set using a map with key as the character and count as the value
• Finally verify the map for which of the characters the count matches the given N

 

Solution

#include <iostream>
#include <string>
#include <map>
#include <vector>

using namespace std;

void remove_dup(string& gems) {
    map<char, bool> visited;
    int len = gems.length();
    int i = 0;
    while(i < len) {
        if(visited[gems[i]]) {
            gems.erase(i, 1);
            len--;
            continue;
        }
        visited[gems[i]] = true;
        ++i;
    }
}

int commons(vector<string>& stones) {
    map<char, int> element_map;
    int commons = 0;
    for(int i = 0; i < stones.size(); ++i) {
        for(int j = 0; j < stones[i].length(); ++j) {
            element_map[stones[i][j]]++;
        }
    }

    for(map<char, int>::iterator it = element_map.begin(); it != element_map.end(); ++it ) {
       if(it->second == stones.size())
           commons++;
    }
    return commons;
}
int main()
{
    int N;
    vector<string> stones;
    cin>>N;
    for(int i=0; i < N; i++) {
        string gem;
        cin>>gem;
        remove_dup(gem);
        stones.push_back(gem);
    }
    cout<<commons(stones)<<endl;
}

• My usual mistakes are in remove_dup. When you erase something in the string, the index goes out of toss. I never gave a thought about it before writing!
• Note that remove_dup does a O(N) operation using map on each of the input string – Is there some other way to make our life easier here??
• Finding commons requires constructing a map of counts for each character. This operation might get slower
• After we find this count, just verifying it whether it is equal to given string count will do our job since remove_dup taken of having our strings unique independently.