string contains unique character
Suggest an algorithm to check if a string contains all unique characters.
Given an integer n, write a function that returns count of trailing zeroes in n!. Examples: Input: n = 5 Output: 1 Factorial of 5 is 20 which has one trailing 0. Input: n = 20 Output: 4 Factorial of 20 is 2432902008176640000 which has 4 trailing zeroes. Input: n = 100 Output: 24
1) Take a buffer of 256 chars (char arr[256];)
ReplyDelete2) 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
@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.
ReplyDelete2) Please keep in mind consideration for Unicode characters also.
hi
ReplyDeletea 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
@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..
ReplyDeleteThis comment has been removed by the author.
ReplyDeletepublic static bool uniqueCheck(string str) {
ReplyDelete// 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;
}
@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