Simply count the substrings
1100, etc. Gets accepted in about 170 ms, which seems to be about as fast as O(n) solutions, even though it's only O(n3).
def countBinarySubstrings(self, s): sum = 0 a = b = '' while True: a = '0' + a + '1' b = '1' + b + '0' add = s.count(a) + s.count(b) if not add: return sum sum += add
Oneliner version, about equally fast:
def countBinarySubstrings(self, s): return sum(itertools.takewhile(bool, (s.count('0'*n + '1'*n) + s.count('1'*n + '0'*n) for n in itertools.count(1))))
Apparently the test suite is quite weak. While the input strings can be up to 50000 characters long, the longest streak of zeros or ones is only 28 long. Because of this, my loop stops fairly early. Even for the pretty small test case
'0' * 1500 + '1' * 1500 my solution would already take over 1 second. I guess the judge's input strings are just random? @contributors