### Reducing a quadratic problem to linear using Dynamic Programming

I've first seen this problem posted by HackerRank , which I thought was super interesting: You're given a string with characters from the alphabet {0,1} (only zeroes and ones allowed), such as "0010". The task is to count the number of sub-strings S that satisfy the following pattern: Length of S must be greater than 0 and even Assume S = S1 + S2 where S1 (and S2) length is equal to half of S length: Either S1 contains only zeros and S2 contains only ones Or S1 contains only ones and S2 contains only zeroes An example makes thinks easier: suppose the input string is "00110". We see the following strings matching S's pattern: S1 = "0 01 10" S2 = " 0011 0" S3 = "001 10 " OK, so the return value here should be 3. Quadratic Solution: An initial quadratic (O(n^2)-time, O(1)-space) can be accomplished in a relatively simple manner: Traverse the string from iterator i = 1..n-1 For each i: Check