GenomicRangeQuery.py

def solution(S, P, Q):
    N = len(S)

    #how many of each are seen
    count = [0]*4
    
    #convert everything to ints for simplicity
    d = [0]*N
    for i in xrange(N):
        if S[i] == 'A':
            d[i] = 1
            count[0]+=1
        elif S[i] == 'C':
            d[i] = 2
            count[1]+=1
        elif S[i] == 'G':
            d[i] = 3
            count[2]+=1
        elif S[i] == 'T':
            d[i] = 4
            count[3]+=1

    M = len(P)
    ans = [0]*M
    
    #catch case if they're all the same
    if   count[0]==count[1] and count[1]==count[2]:
        return [4]*M
    if count[0]==count[1] and count[1]==count[3]:
        return [3]*M
    if count[0]==count[2] and count[2]==count[3]:
        return [2]*M
    if count[1]==count[2] and count[2]==count[3]:
        return [1]*M

    #not all the same, then identify min
    min = 4
    for i in xrange(N):
        if d[i] < min:
            min = d[i]

    for k in xrange(M):

        #short cut case
        if d[P[k]]==min or d[Q[k]]==min:
            ans[k]=min

        else: #naive N*M with some short cuts
            #speed this up to N+M
            low = 4
            for j in xrange(P[k],Q[k]+1): #Q is inclusive

                if d[j] < low:
                    low = d[j]

                    #short cut if min already found
                    if low==min:
                        break

            ans[k] = low

    return ans