4
\$\begingroup\$

I am currently reviewing CTCI(Cracking the Coding Interview)

The question is asking me to implement an algorithm which checks whether the characters in a string are all unique however they do not want me to use any auxillary data structures

My Algorithm is relatively straight forward, Two nested loops one starting at 0(i) and another at 1(i+1)

If the condition finds two characters that are equal then I print duplicate characters have been found.

 public static void checkUnique(String s)
{


    for(int i = 0; i<s.length(); ++i)
    {
        for(int j = i +1; j<s.length(); ++j)
        {
            if(s.charAt(i) == s.charAt(j))
            {
                System.out.println("Duplicates found");
            }
        }
    }


}

My question

  1. Is this an optimal algorithm, my second approach was to sort, and find a pair which contains the same characters.
  2. Obviously a hashmap would be beneficial here, but questions does not really want me to use it.

I have refactored the code and hopefully now it is correct.

Is there any way of reducing it to an O(N) runtime. What if we keep track of the Unicode code's for each char character. I doubt O(N^2) is the best we can do here.

\$\endgroup\$
13
  • \$\begingroup\$ Your implementation Is O(n^2) indeed. The sort approach would get you to O(n * log(n)). You can get to O(n) using a hashset. You can also do it in O(n) using an array of bools of size 256, which would effectively emulate a hashset for 1-byte characters. Not sure from what you wrote if you should not use data structures from standard library or if you are even asked to not implement them on your own... \$\endgroup\$
    – slepic
    Jul 22, 2020 at 13:29
  • \$\begingroup\$ Oh actually, your implementation Is O(n) but that's because It's flawed. It just does not do what you claim it does. That makes your question off topic here. Please test your code before posting the next time. \$\endgroup\$
    – slepic
    Jul 22, 2020 at 13:37
  • \$\begingroup\$ How so, I have tested the inputs "abcdefghijklmnopqrstuvwxyz", it worked, similarly if included duplicate characters it still worked. Am i missing something here \$\endgroup\$ Jul 22, 2020 at 13:44
  • 2
    \$\begingroup\$ Love the question, but I voted to close since this is not working code. Please update the question with working code (include tests!!) so that after we can vote to re-open \$\endgroup\$
    – konijn
    Jul 22, 2020 at 14:08
  • 1
    \$\begingroup\$ For those in the VTC queue, the edit should fix the question. \$\endgroup\$
    – pacmaninbw
    Jul 22, 2020 at 15:43

3 Answers 3

6
\$\begingroup\$

A way to optimize it would be to return as soon as you have found a duplicate, unless the question specifically asks you to list all duplicates.

You could refactor it to something like that:

public static boolean checkUnique(String s) {
    int len = s.length();
    for (int i = 0; i < len; i++) {
        int c = s.codePointAt(i);
        int next = s.indexOf(c, i + 1);
        if (next > i) {
             return false;
        }
    }
    return true;
}

It isn't more efficient as your solution, but I doubt there is an algorithm that can do it better.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Early return sure. But lastIndexOf can only decrease performance. Further there Is also no point to use i++ over ++i, why you even mention it? \$\endgroup\$
    – slepic
    Jul 23, 2020 at 3:24
  • \$\begingroup\$ lastIndexOf can decrease performance compared to what? I mentioned i++ because I find that easier to read. \$\endgroup\$ Jul 23, 2020 at 5:05
  • \$\begingroup\$ Compared to scanning only those characters that can change the result. In every iteration you're going to scan one more character then you need to (unless you find a duplicate). But that's miniscule anyway. And for i++ being easier to read, that's just subjective. Either be explicit about that being your personal opinion or don't include it in your answer at all, as the answer should not be opinion based. \$\endgroup\$
    – slepic
    Jul 23, 2020 at 5:21
  • \$\begingroup\$ Ok, I changed both in my answer. \$\endgroup\$ Jul 23, 2020 at 7:13
1
\$\begingroup\$

If I were your interviewer, I'd not hire you, because of that piece of code.

The one absolute showstopper is that your method prints to System.out instead of returning a boolean.

Even if no one told you explicitly, from a professional developer we expect that algorithms just compute something and give the results to their callers (by means of a boolean return value), and not write it to the user. But your solution mixes the algorithm with text output.

Otherwise, your solution is okay, given the condition that no additional data structure is to be used (by the way, that's a strange condition, not representative for professional development).

\$\endgroup\$
7
  • \$\begingroup\$ What if I told you the solution in the book uses an int as a bitset to store occurrences? Would that count as an auxiliary data structure? stackoverflow.com/questions/19484406/… \$\endgroup\$
    – spyr03
    Jul 22, 2020 at 15:48
  • 1
    \$\begingroup\$ @spyr03 Even with ASCII, the int need to be at least of the 128-bit variant, and in 2020, ASCII is simply outdated. With Unicode, you'd need an unlimited-length-integer (or at least some 200kbit), and that surely is an auxiliary data structure. And don't fall into the trap of operating on the UTF-8 representation bytes, that one will give wrong results. \$\endgroup\$ Jul 22, 2020 at 15:58
  • 1
    \$\begingroup\$ So much this, you stole my answer ;) \$\endgroup\$
    – konijn
    Jul 22, 2020 at 16:13
  • \$\begingroup\$ Yea, I forgot to remove this. The Print was for testing purposes. My bad. \$\endgroup\$ Jul 22, 2020 at 16:23
  • \$\begingroup\$ "...given the condition that no additional data structure is to be used (by the way, that's a strange condition, not representative for professional development)." - hardly, if the professional development environment is for embedded or high-performance computing. If I'm working on some wearable device and I've got 16KB to use for everything, I will be bending over backwards to avoid allocating additional data structures. Granted, that might not be the case on Windows or web servers or even in mobile phones nowadays, but even so. \$\endgroup\$ Jul 23, 2020 at 14:37
1
\$\begingroup\$

I realize that this is old, but I just saw it today and don't see anyone else making this point explicitly.

I doubt O(N^2) is the best we can do here.

It absolutely is not. As you outlined, you can sort the data to find the answer. It's possible to implement a sort in loglinear (\$\mathcal{O}(n \log{n})\$) time and constant space (Heap Sort; Shell Sort). You can either modify the sort to return if it finds a duplicate or just scan the sorted results in linear time. Note that this solution won't work well in Java because a String is immutable. But if you could switch the input from a String to some manipulable data type (e.g. a character array), you could sort that in constant space. And languages like C can sort characters in strings that way (because C stores strings as character arrays and offers direct access to the underlying array).

If you are allowed an auxiliary data structure of the same size as the alphabet, you could find an answer in linear time. For example, if the string can contain only lowercase letters, you could do it within a 32-bit integer (or a 26-bit integer, but that is uncommon size). However, that won't work if the string can contain any UTF-8 character. I mean, you could still build the data structure and it could be constant size (relative to the input length). But the size would be 2²¹ = 2,097,152 bits or bytes or words or whatever (UTF-8 has a direct translation to UTF-32 and only requires 21 bits of that for all current characters). So if you use one bit per character, full UTF-8 still requires 262,144 bytes even if you map the characters to simple integer indexes.

This seems like a rather cheesy use of the term "constant" space, but it is arguably accurate. I would prefer the description linear in the alphabet size, but it is certainly constant if you consider the alphabet size to be constant. And in the specific example of a 26-letter Latin alphabet, it could be represented by a 32-bit integer.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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