The first solution that comes to mind is to use use nested loops..But then we realize that it's a O(n^2) solution.
So we need to refine this solution. A better option than arrives to have an additional array that stores count of each character. This solution is better off than the previous one as it's running time has reduces to O(n). But this one consumes O(n) extra memory.
Can we do it in linear time with constant memory?
If yes, then how?
After thinking some way out, I found this solution:
We can take an(or some) integer variable(s) that will store information like metadata. That will help to know whether a character is duplicated or not.
PS: I've considered lower case alphabets without spaces. Other cases can also be handled..(Thanx 2 Mohan sir 4 small correction.. :) )
So we need to refine this solution. A better option than arrives to have an additional array that stores count of each character. This solution is better off than the previous one as it's running time has reduces to O(n). But this one consumes O(n) extra memory.
Can we do it in linear time with constant memory?
If yes, then how?
After thinking some way out, I found this solution:
We can take an(or some) integer variable(s) that will store information like metadata. That will help to know whether a character is duplicated or not.
int chk = 0;
for(int i = 0; i < strlen(array); i++)
{
if(chk & (1<<(array[i] - 'a'))
return false;
chk |= 1<<(array[i] - 'a');
}
PS: I've considered lower case alphabets without spaces. Other cases can also be handled..(Thanx 2 Mohan sir 4 small correction.. :) )
this solution is good...but wanna ask that in the second method that u mentioned and didn't adopted do we really need O(n) extra space??? I mean we know that the number of characters are limited(i.e. 255)...then y would you need O(n) space???
ReplyDeletePlease give a code to remove duplicates from a string using this logic that takes O(n) time and O(1) space...
ReplyDeleteYou can always use bit fields for this purpose..create a bitfield or an array of integers!
Delete