substringpair.py

"""
Given a string s, count the number of triplets i <= j < k such that
    the substrings s[i:j] and s[j+1:k] have the same set of unique characters.
Algorithm:
    Scan the array, remembering the last time each character appeared
    Use this information to count the number of times each set of characters
        appear in substrings ending at each position (max 26 such sets)
    Repeat for reversed string to count for substrings starting at each position
    For each j, scan through the sets for substrings ending at j and starting at j+1
    If the sets are the same, the product of their counts is the number of
        valid triplets with given j
"""
from sortedcontainers import SortedList
from itertools import pairwise


def get_masks_counts(s):
    last, order, ret = {}, SortedList(), []
    for i, c in enumerate(s):
        if c in last:
            order.remove((-last[c], c))
        last[c] = i
        order.add((-i, c))

        current_masks, mask = [], 1 << order[0][1]
        for (pos1, c1), (pos2, c2) in pairwise(order):
            current_masks.append((mask, pos2 - pos1))
            mask |= 1 << c2
        current_masks.append((mask, 1 - order[-1][0]))
        ret.append(current_masks)
    return ret


s = 'ababac'
s = [ord(c) - ord('a') for c in s]
left, right = get_masks_counts(s), get_masks_counts(s[::-1])[::-1]

ret = 0
for i in range(1, len(s)):
    for (mask1, count1), (mask2, count2) in zip(left[i - 1], right[i]):
        ret += count1 * count2 if mask1 == mask2 else 0
print(ret)