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.
Takeaways:
(1) you can use "accumulator" arrays to store the number of occurences of each letter from 0 to an index, in O(N). Then you can lookup the number of letters between i and j in O(1) subsequently, by taking a difference. (2) You can use these to create an array of 26 integers for each substring, noting the count of each letter, which only needs to be done once, in O(N^2), because there are N*(N+1)/2 substrings. (3) You can sort this array once, which is therefore done in O(log N * N^2), which is the time complexity. (4) You can then go through this array once, counting the number of times there is a repeated anagram (equal arrays). (5) Finally you can get the final answer by summing R*(R-1)/2 for each repeated anagram, which is a math formula based on the sum from 1, 2, 3 .. R - 1. (See the link for an implementation in C++.)
I think you could do better than this if you replaced the sort with a hash table (C++ unordered_map) for counting.
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 →
Yes, it is possible to do better. This passes all tests in 0.01s. I guess I assumed that the tests would be harder.
https://www.hackerrank.com/challenges/sherlock-and-anagrams/submissions/code/21304431
Takeaways: (1) you can use "accumulator" arrays to store the number of occurences of each letter from 0 to an index, in O(N). Then you can lookup the number of letters between i and j in O(1) subsequently, by taking a difference. (2) You can use these to create an array of 26 integers for each substring, noting the count of each letter, which only needs to be done once, in O(N^2), because there are N*(N+1)/2 substrings. (3) You can sort this array once, which is therefore done in O(log N * N^2), which is the time complexity. (4) You can then go through this array once, counting the number of times there is a repeated anagram (equal arrays). (5) Finally you can get the final answer by summing R*(R-1)/2 for each repeated anagram, which is a math formula based on the sum from 1, 2, 3 .. R - 1. (See the link for an implementation in C++.) I think you could do better than this if you replaced the sort with a hash table (C++ unordered_map) for counting.