/*
 * Write a function to check if a string array has duplicate characters. you can
 * assume that the array will only contain characters "a-z". You can not use any
 * additional data structures, or modify the original string array.
 */
#include <stdio.h>
#include <string.h>

/* Basic double loop: O(n^2); n = strlen(input_str) */
int method1(char *input_str)
{
  int i,j;
  char current_chr;

  for(i=0; i<strlen(input_str); i++) {
    current_chr = input_str[i];
    for(j=i+1; j<strlen(input_str); j++) {
      if (input_str[j] == current_chr)
        return 1;
    }
  }
  return 0;
}

/*
 * Use an array to store counts of repeats.
 * Index based on the ascii value.
 * Cost: O(n); n = strlen(input_str)
 */
int method2(char *input_str)
{
  unsigned int counters[128] = {0}; // a-z: 97-122
  int i;

  for (i=0; i<strlen(input_str); i++) {
    if (counters[input_str[i]] > 0)
      return 1;
    else
      counters[input_str[i]]++;
  }
  return 0;
}

/*
 * Uses just 4 bytes (int) to check for repeats
 * Remember ascii values: a(97) z(122)
 */
int method3(char *input_str)
{
  int bits = 0; // bit field
  int i;
  int pos = 0;

  for (i=0; i<strlen(input_str); i++) {
    pos = 1 << (input_str[i] - 'a'); // Get index in the bit field (bits)
    if (bits & pos) // Check if was already seen
      return 1;
    else
      bits |= pos; // Toogle bit if not
  }
  return 0;
}

/*
 * Same as method 3; nirav approach
 */
int nirav_method3(char * input_str)
{
  int result = 0;
  int diff;
  int i;

  for(i=0; i<strlen(input_str); i++)  {
    diff = input_str[i] - 'a';
    diff = 1 << diff;
    if((result & diff) != 0)
      return 1;
    result = result | diff;
  }
  return 0;
}

int main(int argc, char *argv[]) // FIXME: Check input
{
  char *input_str = argv[1]; // FIXME: check is not NULL

  printf("%s: %d\n", input_str, method1(input_str));
  printf("%s: %d\n", input_str, method2(input_str));
  printf("%s: %d\n", input_str, method3(input_str));
  printf("%s: %d\n", input_str, nirav_method3(input_str));
  return 0;
}