Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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)$?
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:
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.
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)$.
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.
