codolove's blog

Solving "Another Problem On Strings — codeforces" using two pointers

By codolove, history, 9 years ago, In English

I was trying to solve Another Problem On Strings using two pointers since it was mentioned in its tags but I am not getting an idea of it. I have solved it by using hashing and binary search by considering the prefix sum. It will be helpful if one can give some idea of approaching it with two pointers.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Let

  • pnt1[i] = maximum j which contains strictly lesser than k+1 "1" in interval [i, j-1].
  • pnt2[i] = maximum j which contains strictly lesser than k "1" in interval [i, j-1].

calculating both are a trivial two pointer exercises.

Now answer is Sum(pnt1[i] — pnt2[i]) for all i = [0, len-1].

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve it by dp? It has 'dp' tag too.

→ Reply