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.
- Special String Again
- Discussions
Special String Again
Special String Again
Sort by
recency
|
788 Discussions
|
Please Login in order to post a comment
The
__repr__
of theruns
class isn't necessary, but it's useful for showing the runs that are found in the string when stepping through the function. We pad the list of runs with "empty" values at the beginning and end to prevent the need for handling edges in the next step.We then iterate through the list of runs, considering each run as a possible candidate to be the middle of a special palindrome (e.g.
aadaa
). We first add the triangle number of its length to the count. If the candidate run has length 1 and its adjacent runs have the same letter, we then add the least of its adjacent runs' lengths to the count.prefix sum algorithm
`long substrCount(int n, string s) { vector left(n, 0), right(n, 0); left[0] = 1; right[n - 1] = 1; for(int i = 1; i < s.size(); i++) { if(s[i] == s[i - 1]){ left[i] = left[i - 1] + 1; } else { left[i] = 1; } } for(int i = n - 1; i >= 0; i--) { if(s[i] == s[i + 1]){ right[i] = right[i + 1] + 1; } else { right[i] = 1; } }
}
JS - fast
(hopefully) easy-to-read O(n) Python solution
I use a deque to keep track of previous counts to find the middle cases. I like this solution because there is a single loop while most other solutions have nested loops.