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.
If i understand your getCount method correctly (you probably loop over the complete input string, right?) your algorithm actually is slower than Racsoth's.
The runtime complexity of your algorithm is O(mn²) where m is the length of s and n the size of the alphabet. To see why think about the worst case: It happens when there is no valid t. Your algorithm will still check all O(n²) letter pairs.
The algorithm of Racsoth has a runtime complexity of O(mn) because for each letter of the input string it only updates O(n) places, no matter how the letter frequencies are distributed.
However, if you slightly modify your code you get an algorithm with good average runtime complexity for random input (maybe even O(mn), I'm not sure). Consider the following sorted frequency distribution:
abcde54321
You only need to check the pairs: (a,b) (b,c) (c,d) (d,e)
This is because the frequency difference for any two letters must be smaller than 2 in an alternating sequence. Try it, you can not make an alternating sequence with 5 'a's and 3 'b's for instance.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Two Characters
You are viewing a single comment's thread. Return to all comments →
If i understand your getCount method correctly (you probably loop over the complete input string, right?) your algorithm actually is slower than Racsoth's.
The runtime complexity of your algorithm is O(mn²) where m is the length of s and n the size of the alphabet. To see why think about the worst case: It happens when there is no valid t. Your algorithm will still check all O(n²) letter pairs.
The algorithm of Racsoth has a runtime complexity of O(mn) because for each letter of the input string it only updates O(n) places, no matter how the letter frequencies are distributed.
However, if you slightly modify your code you get an algorithm with good average runtime complexity for random input (maybe even O(mn), I'm not sure). Consider the following sorted frequency distribution:
You only need to check the pairs: (a,b) (b,c) (c,d) (d,e)
This is because the frequency difference for any two letters must be smaller than 2 in an alternating sequence. Try it, you can not make an alternating sequence with 5 'a's and 3 'b's for instance.