9
\$\begingroup\$

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

\$\endgroup\$
  • 3
    \$\begingroup\$ 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 "?" \$\endgroup\$ – abuzittin gillifirca Feb 7 '14 at 11:44
  • 1
    \$\begingroup\$ Yes 'A' and 'a' are not the same if the question says unique characters, so the toUpperCase() is wrong if so. \$\endgroup\$ – Alfred Armstrong Aug 21 '14 at 9:46
  • \$\begingroup\$ 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. \$\endgroup\$ – Nasir Aug 15 '15 at 6:02
  • 2
    \$\begingroup\$ Notice the subtle off-by-one error in the code - you subtract 64 from the Unicode character (presumed in the range A-Z, i.e. 65-90) but valid indices into chars are 0-25. Including an a and a z in your test cases would expose this error. \$\endgroup\$ – Toby Speight Jul 12 '16 at 7:40
  • \$\begingroup\$ Isn't an array considered a data structure? You're using it as a simple hash table. \$\endgroup\$ – user2023861 Jul 12 '16 at 13:49
6
\$\begingroup\$

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 < 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");
    }
}
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Bobby Feb 6 '14 at 13:51
3
\$\begingroup\$

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");
}
\$\endgroup\$
  • \$\begingroup\$ Horribly inefficient, and isUniquelyComposed("z") doesn't work. \$\endgroup\$ – Roland Illig Sep 11 '17 at 8:14
1
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ isUniquelyComposed("z!") \$\endgroup\$ – Roland Illig Oct 5 '17 at 3:52
0
\$\begingroup\$

I have no idea why all existing answers have the magic number 26 in them, which clearly shows an ASCII- and American-centric world view. A proper solution to this problem must:

  • First discuss whether the word character means char or Unicode code point.
  • Be able to handle arbitrary characters (as defined above).
  • Be a single method with appropriate return type.

Then, the following solutions come to mind:

public static boolean hasUniqueChars(String str) {
    char[] chars = str.toCharArray();
    Arrays.sort(chars);
    for (int i = 1; i < chars.length; i++) {
        if (chars[i - 1] == chars[i]) {
            return false;
        }
    }
    return true;
}

public static boolean hasUniqueCodePoints(String str) {
    int[] cps = str.codePoints().toArray();
    ...
}

The variant without additional data structures (and no heap memory allocation at all) has theoretical time complexity \$O(1)\$ (with a quite large constant factor, MAX_CODE_POINT ** 2), and practical time complexity \$O(n^2)\$, where \$n\$ is the length of the string.

public static boolean hasUniqueCodePoints(String str) {
    int len = s.length();
    if (len > Character.MAX_CODE_POINT) {
        return false;
    }

    for (int i = 0; i < len; ) {
       int cp = s.codePointAt(i);
       if (str.indexOf(cp) != i) {
           return false;
        }
       i += Character.charCount(cp);
    }
    return true;
}

See https://stackoverflow.com/a/1527891.

By the way, the official solution (as of 2017-09-08) is as bad as most code from that book, violating the first two of my requirements.

\$\endgroup\$
-1
\$\begingroup\$

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;
}
\$\endgroup\$
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – Mathieu Guindon Nov 24 '15 at 21:31
  • \$\begingroup\$ I dont think this solution is O(1) ? \$\endgroup\$ – Eduardo Dennis Nov 24 '15 at 22:58
  • \$\begingroup\$ It is O(1) as O(26) is O(1) asymptotically . Correct me if I am wrong . \$\endgroup\$ – Praveen Singh Nov 25 '15 at 9:36
  • \$\begingroup\$ @Praveen You're wrong. Your solution is \$O(\text{s.length()})\$. \$\endgroup\$ – Roland Illig Sep 8 '17 at 0:57
  • \$\begingroup\$ @Roland The solution is O(len(alphabets size)) --> As the alphabet size is fixed so ,it is ultimately O(1) .Explanation: If the string length is more than the distinct alphabets , then by Pigeon Hole principle , the string has duplicate chars. Also s.size() is O(1) as all the string class has internal counter to track the size of the string [link] (cplusplus.com/reference/string/string/size) \$\endgroup\$ – Praveen Singh Sep 29 '17 at 7:20

protected by Community Jun 21 '16 at 23:49

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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