Question: Write an algorithm to find if a string has all unique characters.what if you cannot use additional data-structure?.
Solution: i will write only method(Algorithm).
public boolean isUniqueChar(String str)
{
if(str.lenght() > 256)
return false;
boolean[] char_set = new boolean[256];
for(int a=0; str.length(); a++)
{
int val = str.charAt(a);
if(char_set[val])
{
return false; // because alredy found this char instring
}
char_set[val] = true;
}
return true;
}
Explanation:
Time Complexity for this code is o(n) where n=length of the string.
Space complexity =o(1)
Again once question here,Can we reduce the space complexity? if yes then how?
Solution: yes we can reduce the space complexity using a bit vector.