Determine if a string as duplicate characters

1. Questions

1. Are the characters in the string UTF or ASCII characters, Captial or Non-Captial letters?
2. The length of the string?

2. Naive Solution

A simple solution is to have an integer array with each element being the count of the occurrence of  each characters in the string.

3. Advance and Recursive Solution

A cool trick is to use a bitstring and it works if the characters to check for duplicates is below 32 characters for uint32_t integer.

Recursive

The base case is that is when we reached the zero character. Each recursive call we go one step closer and check  with the integer bit string if the bit for that character is '1', If it is there is a duplicate char or else we continue down the string array.

#include <cstdint>
#include <iostream>

bool CheckUniqueChars(char *string, uint32_t index, uint32_t checker){

 char character = string[index];

 if(character=='\0'){
  return true;
 }else{
  int value = character - 'a';
  
  if((checker&(1<<value))>0){
   return false;
  }else{
     checker |= (1 << value);
     return CheckUniqueChars(string,++index,checker);
  }
 }
}


int main(int argc, char *argv[]){
 
 char *string = argv[1];
 uint32_t idx=0,checker=0;

 if(CheckUniqueChars(string,idx,checker)){
  std::cout << "all characters are unique" << std::endl;
 }else{
  std::cout << "there are duplicate characters" << std::endl;
 }
 
 return 0;
}

4. Discussion

1. Bitstring

Popular Posts