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.