Cpp_Writer's blog

Any O(N log N) solution?
By Cpp_Writer, 7 weeks ago, In English

You are given an integer $$$N$$$, and a string $$$S$$$ of length $$$N$$$ that only contains W and L. How many substrings $$$[l,r]$$$ in $$$S$$$ that satisfies:

  • $$$S_l=S_r=\texttt{W}$$$

  • The value of the count of W in $$$S_{[l,r]}$$$ minus the count of L in $$$S_{[l,r]}$$$ is greater than or equal to $$$K$$$ ($$$K$$$ is an integer and $$$K>0$$$).

  • Vote: I like it
  • -7
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it -27 Vote: I do not like it

I think this can be solved in O(N) only using two pointers.

→ Reply
»
7 weeks ago, # |
  Vote: I like it +30 Vote: I do not like it

you can do prefix sums , then fix the l , count the r with the prefix sum > prefix sum of l + k

this can be done with segment tree or ordered set in nlogn

→ Reply
»
7 weeks ago, # |
  Vote: I like it -17 Vote: I do not like it

maintain two fenwick trees / segment trees/ ordered sets, holding prefix sums ending at W or L

→ Reply
»
7 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

I guess you can do sliding window and solve it in O(N)

→ Reply
»
7 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

not nlog but do a prefix sum where W: 1 and L: -1 then you just 2pointer it

→ Reply