string contains unique character

Suggest an algorithm to check if a string contains all unique characters.

Comments

  1. 1) Take a buffer of 256 chars (char arr[256];)
    2) Now traverse the string char by char
    3) As you encounter the word increment arr[current_char]++;
    4)if the string contains all unique chars then the arr would have either 0 or 1 as elements else >=2

    ReplyDelete
  2. @ankit 1) In place of char array you can take bool array,because we just want to find out whether they repeat or not.we don't need to count them.
    2) Please keep in mind consideration for Unicode characters also.

    ReplyDelete
  3. hi
    a bool array variable has two states false and true... i cant understand how this would help in telling if an element is occurring more than once(i am taking no occurrence as false and occurrence as true).If you want to further reduce the space complexity u can set the bits of an int array.But again a bit can have two states 0,1 so u need to assign 2 bits for a char

    ReplyDelete
  4. @ankit yes you are right since we are interested in finding if a character repeats more than once,so as soon as it is found for first time set its value as 1 and on consecutive occurrence if its value is already one that means it has already occur once so print that character...please check it..

    ReplyDelete
  5. This comment has been removed by the author.

    ReplyDelete
  6. public static bool uniqueCheck(string str) {

    // get the size of characters in the str
    int size = str.Count;

    for (int i=0; i<size-1; i++) {
    if (str.Substring(i + 1, size).Contains(str.Substring(i, 1)))
    return false;
    }
    return true;

    }

    ReplyDelete
  7. @greatI internally for str.Substring(i + 1, size).Contains(str.Substring(i, 1)) will take o(n^2) because for each characters you are comparing it with rest of characters ahead of it.we could do it in linear time.

    ReplyDelete

Post a Comment

Popular posts from this blog