# Algorithm to determine if a string is all unique characters

This my solution to one of the practice problems from Cracking the Coding Interview: 150 Programming Interview Questions and Solutions [Book]

implement an algorithm to determine of a string has all unique characters. What if you cannot use additional data structures ?

public class PracticeProblems {

public void questionOne(String input) {
/*-- implement an algorithm to determine if a string has all unique characters.
* What if you cannot use additional data structures?   --*/

boolean[] chars = new boolean[26];
int x = 0;

for(int i = 0; i < input.length(); i++) {

if(!chars[(int)input.toUpperCase().charAt(i) - 64]) {
chars[(int)input.toUpperCase().charAt(i) - 64] = true;
}
else {
System.out.println("not unique");
x = -1;
break;
}
}

if(x == 0)
System.out.println("unique");
}

public static void main(String[] args) {
PracticeProblems test = new PracticeProblems();
test.questionOne("dsfdddft");
}
}


I was wondering if there was a better solution to this, or if there is a better way of handling the last part, where I am initializing an x variable to be able to determine if I all the characters are not unique, not to print "it is unique". If don't have the condition for the x value it always prints "it is unique".

-
You quote says "unique characters" not unique letters. In Java char can have 2^16 = 65536 different values. What does your program return for this string "?" – abuzittin gillifirca Feb 7 '14 at 11:44
Yes 'A' and 'a' are not the same if the question says unique characters, so the toUpperCase() is wrong if so. – Alfred Armstrong Aug 21 '14 at 9:46
What if a string consists of numbers? In this case, we can have a bool array of 256 (assuming ASCII) and use an ASCII value as an index. – Nasir Aug 15 at 6:02

You probably shouldn't call toUpperCase() twice on each character.

If you wanted to split your code properly (if it was for a real-life project for instance), it would make sense to make the documentaiton a bit better and to define a method taking a String as an argument and returning a boolean. Let's keep things simple for the time being : you can return straight after printing "not unique". If you do so, there's no need for the test on x and there's no need for x at all.

You probably should check that the characters are in the right range before accessing chars.

I'd rather read "if (c) { A } else { B }" than "if (!c) { B } else { A }" even though it depends from one situation to another. In our case, it also allows to remove a level of nesting because of the return.

You don't need an instance of PracticeProblems at all and the function could just be static.

Finally, I do not know if Java optimises out the different call to length so we might ensure we don't call it every time.

public class PracticeProblems {
public static void questionOne(String input) {
boolean[] chars = new boolean[26];
String upper = input.toUpperCase();

for(int i = 0, n = upper.length(); i < n; i++)
{
char c = upper.charAt(i);
if ('A' <= c && c <= 'Z')
{
if(chars[(int)c - 'A'])
{
System.out.println("not unique");
return;
}
chars[(int)c - 'A'] = true;
}
}
System.out.println("unique");
}

public static void main(String[] args) {
questionOne("dsfdddft");
}
}

-
The JVM does a lot of optimizations at runtime based on many factors (and based on which JVM it is). Calling that .length() function for sure isn't a concern at all. – Bobby Feb 6 '14 at 13:51

Well, you don't really need the x variable at all. As soon as you read a repeated character, you could print "not unique" and return from the function, instead of just breaking the loop. Something like:

public void questionOne(String input) {
/*-- implement an algorithm to determine if a string has all unique characters.
* What if you cannot use additional data structures?   --*/

boolean[] chars = new boolean[26];

for(int i = 0; i < input.length(); i++) {

if(!chars[(int)input.toUpperCase().charAt(i) - 64]) {
chars[(int)input.toUpperCase().charAt(i) - 64] = true;
}
else {
System.out.println("not unique");
return;
}
}

System.out.println("unique");
}

-

I would return a boolean from the method that decides what is unique:

public boolean isUniquelyComposed (String word) {

boolean[] alphabetMap = new boolean[26];

for(int index=0, length = word.length(); index < length; index ++)   {
int offsetAsciiCode = (int) word.toUpperCase().charAt(index) - 64;

if(!alphabetMap[offsetAsciiCode])
alphabetMap[offsetAsciiCode] = true;
else
return false;
}

return true;
}

-

If string has only lowercase or upper case characters then you can use this O(1) solution. No extra memory or any additional data structure.

bool checkUnique(string s){
if(s.size() >26)
return false;
int unique=0;
for (int i = 0; i < s.size(); ++i) {
int j= s[i]-'a';
if(unique & (1<<j)>0)
return false;
unique=unique|(1<<j);
}
return true;
}

-
Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and how it improves upon the original) so that the author can learn from your thought process. – Mat's Mug Nov 24 at 21:31
I dont think this solution is O(1) ? – Eduardo Dennis Nov 24 at 22:58
It is O(1) as O(26) is O(1) asymptotically . Correct me if I am wrong . – Praveen Singh Nov 25 at 9:36