SuperSixSubstrings.py

import sys

MEMOIZE = list()
# CANT DO RECURSIVELY IN PYTHON, SO CANT CHECK ON HACKERRANK
# RECURSION LIMIT IS THE PROBLEM

def super_six_substrings(s):
    count = 0

    for i in range(len(s)):
        if s[i] == '0':
            # print(1)
            count += 1
            continue
        ans = substrings_from_index(s, i)
        # print(ans)
        count += ans

    return count


def substrings_from_index(string, index, modulus=0):
    global MEMOIZE

    if index == len(string):
        return 0

    if MEMOIZE[index][modulus] != -1:
        return MEMOIZE[index][modulus]

    num = ord(string[index]) - ord('0')
    MEMOIZE[index][modulus] = substrings_from_index(string, index + 1, (modulus + num) % 3) + (
            (num + modulus) % 3 == 0 and num % 2 == 0)

    return MEMOIZE[index][modulus]


def main():
    global MEMOIZE

    # s = '4806'

    s = '0630033563860000370956238050800516680209600904693616000606306760609036423967006036668033396009509608696766940663696692090040698967204744036340933369020960036063006646986097068660900996000900909969663969068013306749990660334560966660303399936699606661363900603034664686073010629690792205984371600960623666668310608666089066890033590910160378891000764949600836090003636304600689850007861603633556090033669308696298306096406362700308090125809806383090936066633405000690566166003038646027086638097369646663616036060683000678999040906035920460336056086002064663396608608806963460350406994220008014990661007606336360996263663063466002100240149823602868900939033549406082389894665660560466814569068030090938200010006260396056316506629803009632909666636544695486217066300046063697646694610008906630430086038566330006086409683806664046090692646493409026670301033300656828399659303460942279003009034300841300050363333030663333096635606960676124292003539319848350630992023498490696000904960266302975030606940654'

    sys.setrecursionlimit(1000000)

    for i in range(len(s)):
        MEMOIZE.append([-1] * 3)

    print(super_six_substrings(s))


if __name__ == '__main__':
    main()