Skip to content

Instantly share code, notes, and snippets.

@vo
Created March 1, 2014 04:04
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save vo/9284932 to your computer and use it in GitHub Desktop.
Save vo/9284932 to your computer and use it in GitHub Desktop.
Different ways to check for duplicates in a string
#include <iostream>
#include <string>
#include <map>
#include <algorithm>
#include <climits>
// using STL MAP
bool duplicate_check_maphist(std::string s)
{
std::map<char, int> h;
for (int i = 0; i < s.length(); ++i)
if (h[s[i]] == 1) return true;
else h[s[i]] += 1;
return false;
}
// using an array to store histogram
bool duplicate_check_arrayhist(std::string s)
{
int h[255];
for(int i=0; i<255; h[i]=0, ++i);
for(int i=0; i<s.length(); ++i)
if (h[s[i]] == 1) return true;
else h[s[i]] += 1;
return false;
}
// check every pair of characters (O(n^2))
bool duplicate_check_inplace(std::string s)
{
size_t len = s.length();
for(int i=0; i<len; ++i)
for(int j=i+1; j<len; ++j)
if(s[i] == s[j])
return true;
return false;
}
// check using counting every possible char
// technically O(n), efficient for large strings
// (much larger than CHAR_MAX)
bool duplicate_check_inplace_count(std::string s)
{
size_t len = s.length();
for(int i=0; i<=CHAR_MAX; ++i)
if (std::count(s.begin(), s.end(), i) > 1)
return true;
return false;
}
// check by sorting the string and checking for consecutives
// this is kind of a cheap way of doing it.
bool duplicate_check_sort(std::string s) {
std::sort(s.begin(), s.end());
std::string::iterator it = std::adjacent_find(s.begin(), s.end());
return (it == s.end()) ? false : true;
}
int main()
{
// ask user input
std::cout << "Enter a string: ";
std::string s;
std::getline(std::cin, s);
// check the length
bool has_duplicate = duplicate_check_maphist(s);
if (has_duplicate)
std::cout << "There is a duplicate!" << std::endl;
else
std::cout << "There are no duplicates!" << std::endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment