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.


1 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.

  • $\begingroup$ Yes this helps. $\endgroup$ Feb 19 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.