Bliss8's blog

Number of subsequences in a string
By Bliss8, 7 years ago, In English

Recently there was a problem DIV2 A to count subsequences 'QAQ' in given string

There is O(N) solution for that problem: count how many 'Q' we have on a prefix[i], and then for each 'A' res+=prefix[i]*(qTotal - prefix[i]). (multiply number of 'Q's to the left and right from 'A')

But what if we had to count 'QAQAQ' or any other sequence? I would like to get some insights on general solution of the problem.

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

Comments Comments (2)
| Write comment?
»
7 years ago, # |
← Rev. 3   Vote: I like it +4 Vote: I do not like it

Let's suppose in the general problem, we have 2 strings S and T, and we need to count the amount of subsequences in S that are equal to T. Let's denote |S| = n, |T| = k (|a| stands for string a's length).

We can maintain an array dp[k], where each cell dp[i] denotes the amount of subsequences we found until now, that are equal to the first i characters of T (we'll use 1-indexing just to ease on understanding). initially the array dp is set to all 0.

We process S's characters from left to right, let's denote the currect one as C. for each location X so that T[X] = C, we do dp[X] = dp[X] + dp[X - 1]. If one of the X's is 1 (the first character), we do dp[1] = dp[1] + 1. Please note, that we should iterate on these X values from big to small, otherwise, we could be doing something like: dp[2] = dp[2] + dp[1], dp[3] = dp[3] + dp[2], dp[4] = dp[4] + dp[3]..., which shouldn't happen while we're checking a single character in S.

Once we're done, the answer will be in dp[k]. The running time is, on worst case, O(nk)

→ Reply