## Thursday 26 June 2014

### 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.