Even i did it using the same approach but i want to know if someone used a different approach cause it took me some time to figure out this approach.
Yeah, makes sense it’s inneficient, since, as I said, I was not managing to make it run in a decent time, and, looking at it again, it makes sense why this is inneficient, is there any way of solving this using a similar approach to the one I was trying to follow?
What I recommend you is to solve the easier version first. This means you should come up with a solution for the AB strings. Then it’s relatively easy to find the solution for the ABC strings.
The trick to come up with the solution to the easier version is to basically write out every equation you have. For example, the condition is A_j - A_i = B_j - B_i, where A_i - A_j means the number of A characters in the range [i + 1, j]. Now play with the equation, so that we can work with it more flexible. With more experience you will realize that A_j - B_j = A_i - B_i is a good one to work with.
3 Likes
Please fix the solution links and tags are not-consistent.
same here …
Can anyone explain the intuition behind making those pairs in way specified above and searching it ? What kind of problems require this approach ?
Yes, using segment tree it can be solved with O(nlogn) time and space. Each node holds the following information:
(assume f(subarray) denotes a mapping of the substring containing A, B, C to some triplet (x, y, z) where x = #A, y = #B, z = #C)
- Total count of satisfying subarrays in the range
- Set of f(subarray) for each subarray starting at the left end of the range
- Set of f(subarray) for each subarray ending at the right end of the range
- f(range)
The relevant updates are also easy to figure out and allows to solve the whole problem in desired time complexity.
would you please explain your hash i.e. implementation and functionality
mp[make_pair(0,0)]++;
what is the use of this line