CODEWITHSUNDEEP
arraysstringalgorithmc++11data-structures
johndoesnow
johndoesnow

Reputation: 33

Arrays and Strings Cracking the Code Interview 6th ed Soln 1.1

I'm practicing the cracking the code interview on my spare time. The question states: Is Unique: Implement an algorithm to determine if a string has all unique character. What if you cannot use additional data structures?

The solution I found is: https://github.com/careercup/CtCI-6th-Edition-cpp/blob/master/Ch%201.Arrays%20And%20Strings/1.Is%20Unique/1.%20Is_unique.cpp

My implementation is: 

bool UniqueCharsHash(string word) {

    map<char, bool> uniqueChar; //keyType, valueType

    for (int i = 0; i < word.length(); i++) {
        char letter = tolower(word[i]);
        if (!uniqueChar[letter]) {
            uniqueChar[letter] = true;
        } else {
            return false;
        }
    }
    return true;
}

 //O(n^2) run time using a two loops (1 outer and 1 inner)
bool UniqueCharNoDS(string word) {
     for (int i = 0; i < word.length() - 1; i++) {
        for (int j = i + 1; j < word.length(); j++) {
            if (word[i] == word[j]) {
                return false;
            }
        }
    }
    return true;
}

but in the hint portion of the book it states:

  1. try a hash table
  2. could a bit vector be useful
  3. can you solve it in O(Nlogn) time

I was wondering in the 3 methods shown, are any of those NlogN time?

Upvotes: 0

Views: 737

Answers (4)

Jacq
Jacq

Reputation: 105

An O(n) time could be used with the hint (#2) provided. Where you shift bits and flip if a letter has already been seen. 

static boolean isUniqueNoStruct(String input) {

    // Length check
    if (input.length() > 256)
        return false;

    // Assuming only lowercase 32 bit characters
    int checkVal = 0;

    for (int i = 0; i < input.length(); i++) {
        int bit = input.charAt(i) - 'a';

        // If the bit at the index has been flipped return false
        if ((checkVal & ( 1 << bit)) > 0) {
            return false;
        }

        checkVal |= (1 << bit);
    }

    return true;
}

Upvotes: 0

Courage
Courage

Reputation: 792

This code solves it in O(NlogN) time, it is a modification of merge sort

boolean isUnique(char[] arr){
        return sort(arr,0,arr.length-1);
 }

// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
boolean merge(char arr[], int l, int m, int r)
{
    // Find sizes of two subarrays to be merged
    int n1 = m - l + 1;
    int n2 = r - m;

    /* Create temp arrays */
    char L[] = new char [n1];
    char R[] = new char [n2];

    /*Copy data to temp arrays*/
    for (int i=0; i<n1; ++i)
        L[i] = arr[l + i];
    for (int j=0; j<n2; ++j)
        R[j] = arr[m + 1+ j];


    /* Merge the temp arrays */

    // Initial indexes of first and second subarrays
    int i = 0, j = 0;

    // Initial index of merged subarry array
    int k = l;
    while (i < n1 && j < n2)
    {
        if (L[i] < R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else if(L[i] > R[j])
        {
            arr[k] = R[j];
            j++;
        }
        else{
            return false;
        }
        k++;
    }

    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    /* Copy remaining elements of L[] if any */
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }

    return true;
}

// Main function that sorts arr[l..r] using
// merge()
boolean sort(char arr[], int l, int r)
{
    if (l < r)
    {
        // Find the middle point
        int m = (l+r)/2;

        // Sort first and second halves
       boolean left= sort(arr, l, m);
        boolean right  = sort(arr , m+1, r);

        // Merge the sorted halves
     return  left&&right&&merge(arr, l, m, r);
    }
    return true;
}

Upvotes: 0

Ajay
Ajay

Reputation: 1

The below code (in Java) will determine if a string has all unique character.
Time complexity --> O(n)

final static int LETTERS_LEN = 256; 
public static boolean isUnique(String str){

    int[] letters = new int[LETTERS_LEN];

    for (int i = 0; i < str.length(); i++) {
        letters[str.charAt(i)]++;
    }

    for (int i = 0; i < LETTERS_LEN; i++) {
        if (letters[i] > 1) {
            return false;
        }
    }
    return true;
}

Upvotes: 0

rici
rici

Reputation: 241901

As has often been pointed out, this question is solvable in O(1) because the longest string made up of unique characters is 256 characters long.

So when/if your​ algorithm hits the 257th character, it can stop and report "no".

Even if you use the naive algorithm of searching each character in the prefix up to that point, there are a maximum of 255*128 comparisons before the limit is reached. (No adjustment to the algorithm is necessary; it must report "no" on the 257th character if there is one.)

Upvotes: 1

Related Questions