Lol brute force is fast (Python)


  • 0

    Simply count the substrings 01, 10, 0011, 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


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.