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.
I don't really understand the editorial, so here is how I did things. I think it is a bit more intuitive. I looked at it more from a combinatorial perspective. The solution is still O(n), but only needs a single pass through the string.
The total number of ways to remove 2 characters is n choose 2, which is n! / (2 * (n-1)!), or n * (n-1) / 2. However, when there is a streak of duplicates, it doesn't matter which particular spot in the streak we remove, so that reduces our choices. So, we can look at the number of unique streaks of letters of length 1 or more; call this m. So now we are looking at m choose 2 = m * (m - 1) / 2 ways to remove 2 characters (without double counting multiple ways to remove letters from the same streak of duplicates). But wait! We have removed two many choices. We removed the case where we choose both of our letters to be removed from the same streak of duplicates. We need to add those back in. Let d be the number of streaks of 2 or more duplicates. Now, our total is m * (m - 1) / 2 + d.
There is one other pattern that reduces our total number of unique resultant strings. Any time there is a sequence of three letters of the form ABA (so ADA, MQM, etc), we end up with one duplicate. This is because when we remove 2 letters from ABA, we can only end up with A or B. Alternativley, if we choose B, it doesn't matter if we choose the first A or the second A. Call the number of these patterns p and subtract it from our total.
So all we have to do is loop through the string once to find d (the number of streaks of at least two duplicates), m (the total number of streaks of even a single letter), and p (the number of occurences of ABA patterns), and the final formula is m * (m - 1) / 2 + d - p.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Beautiful Strings
You are viewing a single comment's thread. Return to all comments →
I don't really understand the editorial, so here is how I did things. I think it is a bit more intuitive. I looked at it more from a combinatorial perspective. The solution is still O(n), but only needs a single pass through the string.
The total number of ways to remove 2 characters is n choose 2, which is n! / (2 * (n-1)!), or n * (n-1) / 2. However, when there is a streak of duplicates, it doesn't matter which particular spot in the streak we remove, so that reduces our choices. So, we can look at the number of unique streaks of letters of length 1 or more; call this m. So now we are looking at m choose 2 = m * (m - 1) / 2 ways to remove 2 characters (without double counting multiple ways to remove letters from the same streak of duplicates). But wait! We have removed two many choices. We removed the case where we choose both of our letters to be removed from the same streak of duplicates. We need to add those back in. Let d be the number of streaks of 2 or more duplicates. Now, our total is m * (m - 1) / 2 + d.
There is one other pattern that reduces our total number of unique resultant strings. Any time there is a sequence of three letters of the form ABA (so ADA, MQM, etc), we end up with one duplicate. This is because when we remove 2 letters from ABA, we can only end up with A or B. Alternativley, if we choose B, it doesn't matter if we choose the first A or the second A. Call the number of these patterns p and subtract it from our total.
So all we have to do is loop through the string once to find d (the number of streaks of at least two duplicates), m (the total number of streaks of even a single letter), and p (the number of occurences of ABA patterns), and the final formula is m * (m - 1) / 2 + d - p.