current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 5 down vote favorite

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".

share|improve this question
1  
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 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 at 9:46

3 Answers 3

up vote 6 down vote accepted

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");
    }
}
share|improve this answer
    
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 at 13:51
up vote 4 down vote

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");
}
share|improve this answer
up vote 2 down vote

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;
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.