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.
Looking at your solution, it looks like it runs in O(N^3). You compare each substring of equal length. There are O(N^2) such substrings, and each comparison takes O(N), leading to a total running time of O(N^3).
I took a different approach. I used hashing to effectively partition each substring into equivalence classes, based on the counts of the different characters they contained. Because I reuse calculations from one substring to another, this approach takes O(N^2), and is asymptotically more efficient. Take a look at the code I submitted, linked in my original post, to see exactly what I did, and why it's more efficient.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Sherlock and Anagrams
You are viewing a single comment's thread. Return to all comments →
Looking at your solution, it looks like it runs in O(N^3). You compare each substring of equal length. There are O(N^2) such substrings, and each comparison takes O(N), leading to a total running time of O(N^3).
I took a different approach. I used hashing to effectively partition each substring into equivalence classes, based on the counts of the different characters they contained. Because I reuse calculations from one substring to another, this approach takes O(N^2), and is asymptotically more efficient. Take a look at the code I submitted, linked in my original post, to see exactly what I did, and why it's more efficient.