Thursday 26 June 2014

Find the number of letters common in given set of strings



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.


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


The count of common characters across the above 3 strings is only ‘b’
  • 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



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

No comments:

Post a Comment