This idea is implemented by calculating prefix sum first to record the number of appearance of nucleotides in a target string. After that, for each query, it will check whether a nucleotide is a minimum factor or not.

def solution(S, P, Q): records = [[0]*4 for i in range(len(S))] results = [0] * len(P) for i in range(len(S)): if (S[i] == 'A'): records[i][0] = 1 elif (S[i] == 'C'): records[i][1] = 1 elif (S[i] == 'G'): records[i][2] = 1 elif (S[i] == 'T'): records[i][3] = 1 for i in range(1, len(S)): for j in range(4): records[i][j] += records[i-1][j] for i in range(len(P)): head = P[i] tail = Q[i] for j in range(4): sub = 0 if (head - 1 >= 0): sub = records[head-1][j] if (records[tail][j] - sub > 0): results[i] += j + 1 break return results