1
$\begingroup$

I would like to double check myself.

As I understand time complexity of comparing two strings in the worst case is $O(n)$, where $n$ is the length of the strings (let's say they are equal length).

In case I have $N$ strings and I would like to know whether they are all different.

Is there an algorithm for this that is faster than $O(n \cdot N^2)$?

$\endgroup$
3
$\begingroup$

You can sort the strings based on increasing or decreasing lexicographic order. Then, you can easily find the duplicate string by iterating over the set once, and checking if any two consecutive strings are the same or not.

Now, everything boils down to the sorting algorithm that you want to use. Consider these two popular options:

  1. If you use Merge sort, it would take $O(N \log N)$ comparison operations. Since the length of each string is at most $n$, a comparison operation would take $O(n)$ time. Thus, the sorting takes $O(n \cdot N \log N)$ time.

  2. You can also use Radix sort. It would take $O(n \cdot N)$ time. This is similar to the approach that is suggested by gnasher729. I am just explicitly mentioning the name of this technique.

It is easy to see that Radix sort is giving a better time complexity of $O(n \cdot N)$. Lastly, iterating over the entire set once and checking if any two consecutive strings are the same, takes $O(n \cdot N)$ time. Thus, the overall time complexity is $O(n \cdot N)$.

$\endgroup$
3
$\begingroup$

It’s much better. Say you have strings implemented as a sequence of 8 bit characters. You put each string into one of 256 bins depending on the first character. Then you examine the bins with more than one entry, by putting strings into bins depending on the second character and so on.

The worst case is all strings starting with the same $k$ characters for $k$ close to $n$; this is handled in $O(kN)$ steps. Your algorithm suffers badly in this case.

$\endgroup$
1
  • 1
    $\begingroup$ You can even go 1 bit at a time (so just 2 bins), regardless of the alphabet size. $\endgroup$ – j_random_hacker Jan 12 at 4:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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