How did so many people get D right ? more than 2000 ppl got AC, just curious, my Approach was F[i] be the answer if string starts from i,
if(str[i]==str[i+1])
F[i] = F[j] + 1
where j is the first index diff from i,
else
F[i] = F[i+2] + 1
, this approach though wrong, seemed extremely obvious, so those who sovled it in contest did you land on the right approach initially itself, or did you land on the above mentioned approach then realized it's wrong and then moved on ?
I had a similar approach, but unable to think of other approach, help would be appreciated
My logic was: Process the indices one by one, from the left. Each time add $$$1$$$ to the answer. In each iteration of $$$i$$$, find the first index $$$j$$$ such that $$$str[j]==str[j+1]$$$, and remove $$$str[j]$$$. If such a $$$j$$$ doesn't exist, then just remove $$$str[i]$$$. I used two-pointers to implement this.
My code isn't very clean, but you can refer to it, if it helps: here.
I didn't ask the approach, I just wanted to know if you landed on the right approach initially itself, I mean did you think about the above mentioned approach ?
No, I didn't think of the above approach.
Actually I don't even understand the idea above so I guess I haven't thought about it.
I did the same then moved to another approach...but failed! Though the problem was not that tough, still confused how so many people solved it!
Here is how I approached.
At first, notice that in each step some block of same numbers will be removed from the prefix. We can only decrese size of the block by one(using 1st part of operation) and it's not optimal to remove the block of size one, because it will concatinate other two neighbouring blocks. So idea is to use something like deque, we push back elements from left to right and when we have block of size greater than 1, we will do operation there.