CTCI: Ch. 1-1

Posted on by

Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures? 

​ 

#include <iostream>
#include <string.h>
using namespace std;
bool checkUnique(char *str);

bool checkUnique(char *str)
{
    // string length is less than 256
    if(strlen(str) > 256)
        return false;
    
    int charArray[256] = {};
    for(int i=0;i<strlen(str);i++)
    {  
        charArray[(int)str[i]]++;
        if(charArray[str[i]] > 1)
            return false;
    }
    return true;
}

int main(int argc, const char * argv[])
{
    char ch[]= "qazwsxedcrfvyhnujm";
    if(checkUnique(ch))
        cout<<"UNIQUE"<<endl;
    else
        cout<<"NOT UNIQUE"<<endl;
    return 0;
}

Time Complexity: O(n)

Space Complexity: O(1)

One thought on “CTCI: Ch. 1-1”

  1. Initialize an array in C/C++ 

    int arr[10] = {}; //all elements 0 in C++
int arr[10] = {0}; //all elements 0 in C

    in C: 

    int arr[10];
arr[0] = 1638232
arr[1] = 4210996
arr[2] = 4279408
arr[3] = 4242269
arr[4] = 0
arr[5] = 4255816
arr[6] = 2130567168
arr[7] = 4280492
arr[8] = 1
arr[9] = 256
    int arr[10]={0}; //int arr[10]={}; compile error
arr[0] = 0
arr[1] = 0
arr[2] = 0
arr[3] = 0
arr[4] = 0
arr[5] = 0
arr[6] = 0
arr[7] = 0
arr[8] = 0
arr[9] = 0

    in C++: 

    int arr[10];
arr[0] = 1638232
arr[1] = 4210996
arr[2] = 4279408
arr[3] = 4242269
arr[4] = 0
arr[5] = 4255816
arr[6] = 2130567168
arr[7] = 4280492
arr[8] = 1
arr[9] = 256
    int arr[10]={0}; // or int arr[10]={};
arr[0] = 0
arr[1] = 0
arr[2] = 0
arr[3] = 0
arr[4] = 0
arr[5] = 0
arr[6] = 0
arr[7] = 0
arr[8] = 0
arr[9] = 0

     

Leave a Reply