Palindromic subsets brute solution

palindromic_subsets_brute_sol.py

MOD = 10 ** 9 + 7


def modpow(x, y, mod):
    elems = []
    while y:
        elems.append(y % 2)
        y >>= 1
    el = len(elems)
    x_pows = [x for _ in xrange(el)]
    for i in xrange(1, el):
        x_pows[i] = (x_pows[i - 1] * x_pows[i - 1]) % mod

    ret = 1
    for i in xrange(el):
        if elems[i] == 1:
            ret = (ret * elems[i] * x_pows[i]) % mod
    return ret


def palindromes(counts, mod):
    counts = [c for c in counts if c != 0]
    lc = len(counts)
    evens = [modpow(2, count - 1, mod) for count in counts]

    ret = 1
    for even in evens:
        ret = (ret * even) % mod

    # We need to substract 1 for the empty palindrome
    ret = (ret * (len(counts) + 1) - 1) % mod
    return ret


def rev(ch):
    return ord(ch) - 97


def simple_build(string):
    n = len(string)
    counts = [[0] * n for _ in xrange(26)]

    for i, ch in enumerate(string):
        if i == 0:
            counts[ch][0] = 1
            continue
        for j in xrange(26):
            counts[j][i] = counts[j][i - 1] + (1 if ch == j else 0)

    return counts


def simple_shift(counts, fr, to, t):
    lc = len(counts[0])
    string = [0] * lc
    for i in xrange(26):
        if counts[i][0] == 1:
            string[0] = i
            break
    for j in xrange(1, lc):
        for i in xrange(26):
            if counts[i][j] != counts[i][j - 1]:
                string[j] = i
                break
    for j in xrange(fr, to + 1):
        string[j] = (string[j] + t) % 26
    return simple_build(string)


def simple_query(counts, fr, to):
    ret = []
    for i in xrange(26):
        if fr == 0:
            ret.append(counts[i][to])
        else:
            ret.append(counts[i][to] - counts[i][fr  - 1])
    return ret


n, q = map(int, raw_input().strip().split())
string = raw_input().strip()
string = [rev(ch) for ch in string]

counts = simple_build(string)

for _ in xrange(q):
    query = map(int, raw_input().strip().split())
    if query[0] == 1:
        counts = simple_shift(counts, *query[1:])
    else:
        ccounts = simple_query(counts, *query[1:])
        print palindromes(ccounts, MOD)