We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
this part takes O(NlogN) time because It is a comparison sort according to C++ docs. If you use an counting sort instead, you will achieve O(N) time sorting even though I'm not sure C++ standard library provides you a counting sort function.
Basically, you don't even need to sort it. If you can come up with a hash function which only considers numbers of occurences of each letter, not position, you can get by. That is 'abc' and 'cba' should be considered to be the same seed. I kinda did this thing in my code.
I'm not good enough at C++, so I don't think I can write you a succinct code snippet for it.
Sherlock and Anagrams
You are viewing a single comment's thread. Return to all comments →
this part takes O(NlogN) time because It is a comparison sort according to C++ docs. If you use an counting sort instead, you will achieve O(N) time sorting even though I'm not sure C++ standard library provides you a counting sort function.
Basically, you don't even need to sort it. If you can come up with a hash function which only considers numbers of occurences of each letter, not position, you can get by. That is 'abc' and 'cba' should be considered to be the same seed. I kinda did this thing in my code.
I'm not good enough at C++, so I don't think I can write you a succinct code snippet for it.