solution to https://codeforces.com/problemset/problem/1426/F

subseq.py

import sys
from time import perf_counter

class SequenceDiscoveryNode:
    def __init__(self, parent, value):
        self.parent = parent
        self.children = []
        self.value = value

    def construct_tree(self, remaining_sequence: list):
        if len(remaining_sequence) == 0:
            return self
        else:
            next_char = remaining_sequence.pop(0)
            if next_char is "a" or next_char is "b" or next_char is "c":
                node = SequenceDiscoveryNode(self, next_char)
                self.children.append(node.construct_tree(remaining_sequence))
            else:
                node_a = SequenceDiscoveryNode(self, "a")
                node_b = SequenceDiscoveryNode(self, "b")
                node_c = SequenceDiscoveryNode(self, "c")

                child_a = node_a.construct_tree(remaining_sequence.copy())
                child_b = node_b.construct_tree(remaining_sequence.copy())
                child_c = node_c.construct_tree(remaining_sequence.copy())

                self.children = [child_a, child_b, child_c]
            return self

    def get_terminus_nodes(self, final_nodes=[]):
        if len(self.children) > 0:
            for child in self.children:
                child.get_terminus_nodes(final_nodes)
        else:
            final_nodes.append(self)

    def traverse_backwards(self):
        if self.parent:
            parent = self.parent
            return self.value + parent.traverse_backwards()
        else:
            return self.value


def count_subsequences(sequence):
    class SubSeq:
        def __init__(self, value=0):
            self.value = value

        def update(self, char):
            if char == self.value + 1:
                self.value = char

        def count(self):
            if self.value == 2:
                return 1
            else:
                return 0

    subseqs = []
    for char in sequence:
        if char == 'a':
            subseqs.append(SubSeq())
        elif char == 'b':
            for subseq in subseqs:
                subseq.update(1)
        elif char == 'c':
            for subseq in subseqs:
                subseq.update(2)
    count = sum([subseq.count() for subseq in subseqs])
    return count


def run(input):
    tree_root = SequenceDiscoveryNode(None, "")
    t0 = perf_counter()
    input_sequence = [char for char in input]
    tree = tree_root.construct_tree(input_sequence)
    t1 = perf_counter()
    terminus_nodes = []
    tree.get_terminus_nodes(terminus_nodes)
    t2 = perf_counter()
    reversed_sequences = [tip_node.traverse_backwards()[::-1] for tip_node in terminus_nodes]
    t3 = perf_counter()
    count = sum([count_subsequences(sequence) for sequence in reversed_sequences])
    t4 = perf_counter()
    print("{}\n{}\n{}\n{}\n{}".format(str(t1-t0), str(t2-t1), str(t3-t2), str(t4-t3), str(t4-t0)))
    return count


if __name__ == "__main__":
    _ = input()
    data = input()
    print(run(data))
    sys.exit()