number of substrings in same position with same contents

Question

L1 and L2 are two lists which only consist of X's and Y's. L1 and L2 have the same length.

How many sublists of L1 contain the same number of X's as the sublist of L2 in the same position? The empty sublist is not counted.

For example:

1. L1 = X L2 = Y => return 0

2. L1 = Y, Y L2 = Y, Y => return 3

3. L1 = Y, X, Y L2 = X, Y, X => return 2

4. L1 = Y, Y, X, X L2 = X, X, Y, Y => return 2

A brute-force approach would have time complexity O(n^2). I think (but I am not sure) there's an O(n) solution, but I can't put my finger on it.

Answer 1

You are right, there is an $O(n)$ time algorithm for this.

Let $L(i,j)$ be the substring of the string $L$ from index $i$ to $j$, and let $|L|_X$ be the number of $X$'s in $L$. Consider that the number of substrings ending on an index $j$ with the same number of $X$'s in both strings is equal to the number of indices $i$ (with $i<j$) for which $$|L_1(1,i)|_X - |L_2(1,i)|_X = |L_1(1,j)|_X - |L_2(1,j)|_X$$ Hope this helps.