CareerCup

Normally u would use a set for that. But if you can restrict the range of characters to ASCII (vs. Unicode for example) you can use an array of booleans or a bit vector. Just mark every character as seen[S.charAt(I)] = true after checking seen[s.charAt(I)] ... I think you get the idea. This has time complexity O(n) and space complexity O(n).

Your solution is of space complexity O(1) but time complexity O(n^2). That square comes from contains that will loop from 0 to i, where i is looped from 0 to n. So n^2 / 2 to be exact...

edit:
no, it's not O(n^3) because substring(..).contains() is not nested (although a bit unnecessary copying...)

If you are allowed to change the string you are given you can sort it and then looking for duplicates can be done in O(n); so the total is O(nlog(n)) for the sort;
If you cannot do that you must search the whole string for each letter you run across. Of course you can double the speed by only looking forward from where you are.
this will cost you O(n^2)

for(int i =0; i < len-1; i++)
{
    for(int j = i+1; j < len; j++)
    {
	if(input[i] == input[j]) return false;
    }
}
return true;

As per my analysis, I think that it would take O(n^3) where n is the size of string. Since outer loop runs O(n) time, then substring method O(n) and contains O(n). I think a better approach that runs in O(n^2) time, similar to your approach is that (Pseudo code)

for each char in string:
	i <-- position of char in string
	for j from i-1 to 0:
		if charAt(i)==charAt(j)
			return false;
return true;

public class HelloWorld{
  public static void main(String...args){
   	String s=args[0];
    int a=0;
    for(int i=0;i<s.length();++i){
      int bit=1<<(s.charAt(i)-'a');
      if((a | bit) == a){     // If there is no change after OR operation, then it's a repeatition.
        System.out.println("Yes");
        return;
      }
      a=a | bit;
  	}
    System.out.println("No");
  }
}

It can be done in one loop i.e. 0(n) to determine if string has all unique characters without extra space complexity O(1).
int xor=0;
for(int i=0;i<str.length();i++){
xor=xor^(int)str.charAt(i);
}

return (xor==0);
}

@smile.jain, your approach will not work. Consider the string str = "ABC", XOR of each character is not zero so your function will return false, but for given string ans is true as it contains all unique character.

Free hand code, O(n) space and time

boolean isUnique(String str){
Map<Character, Boolean > map = new HashMap<String, Boolean>;

for(Character c : str.toCharArray()){
if(map.ContainsKey(c)){
return false;
} else {
map.put(c);
}
return true;
}