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 &lt; 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 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 documentation 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 immediately 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 &lt; n; i++)
        {
            char c = upper.charAt(i);
            if ('A' &lt;= c &amp;&amp; c &lt;= '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");
    }
}