Longest palindromes in a string

Question

Honestly, I'm doing a practice and get blocked. Problem link.

The problem is simple, given a string, calculate the number of max length palindromes (Any substring is valid, which means you can take any chars you want and reorder them as you want). Return the result modulo 1000000007.

For example, given amim, the answer is 2 (mim and mam).

Full Code

#!/bin/python3

import math
import os
import random
import re
import sys
from itertools import permutations
from functools import lru_cache

# Complete the initialize function below.
def initialize(s):
    # This function is called once before all queries.
    s = [ord(i) - 97 for i in s]
    results = [[0] * 26]
    for i, v in enumerate(s):
        result = results[i].copy()
        result[v] += 1
        results.append(result)
    return results

def count(s):
    result = [0] * 26
    for i in s:
        result[i] += 1
    return result

factorial = lru_cache(None)(math.factorial)

p = 1000000007

pow = lru_cache(None)(pow)

# Complete the answerQuery function below.
def answerQuery(l, r):
    # Return the answer for this query modulo 1000000007.
    counted1 = counted_list[l - 1]
    counted2 = counted_list[r]
    counted = [counted2[i] - counted1[i] for i in range(26)]
    left = 0
    total = 0
    divide = []
    for temp in counted:
        left += temp & 1
        total += temp >> 1
        divide.append(temp >> 1)
    total = factorial(total)
    total = total % p
    for i in divide:
        temp = factorial(i)
        temp = pow(temp, p - 2, p)
        total = total * temp
    result = total * (left or 1)
    return result % p


if __name__ == '__main__':
    s = input()

    counted_list = initialize(s)
    q = int(input())

    for q_itr in range(q):
        lr = input().split()

        l = int(lr[0])

        r = int(lr[1])

        result = answerQuery(l, r)

        print(result)

The code above can pass #0~#21 testcases and will fail in #22 due to timeout. (Just copy it to Problem link page given at the top)

As #22 testcase is very huge, I cannot post it here. So here is the link:

https://files.fm/u/mekwpf8u

If I can use numpy to rewrite this function, I think it will be better. But I cannot, I can only use the standard libs.

update

I use another customized factorial function but exceed memory usage limitation :/ But it really reduces the total time cost.

factorial_table = [1, 1]
def factorial(n):
    if n < len(factorial_table):
        return factorial_table[n]

    last = len(factorial_table) - 1
    total = factorial_table[last]
    for i in range(last + 1, n + 1):
        total *= i
        factorial_table.append(total)

    return total

Answer 1

• Do % p early.

  Since the test case is huge, I expect intermediate values you compute to be huge as well. Multiplication of large numbers is a very expensive operation. Try to keep your results in a native range. Consider e.g.

  def modulo_factorial(n, mod):
      result = 1
      for i in range(1, n + 1):
          result = (result * i) % mod
      return result
  

  Ditto for pow.

• Do not recompute factorials from scratch. Instead of

  for i in divide:
      temp = factorial(i)
      temp = pow(temp, p - 2, p)
      total = total * temp
  

  sort divide first. Then computation of each factorial can be started where the previous one ended.

  Also notice that since total is greater than any element of divide, you should compute factorial(total) after the this loop, using the same technique.

  And don't forget to % p early.

• Most of your imports are never used.