We can calculate distances from the current position (i=0,1,...,N-1) to the nearest previous nucleotide for each type of nucleotide, where all previous nucleotides and the current one (at current position) are considered.
The distances array pre_dists will be something like:
| C A G C C T A |
----|-----------------------------------|
A | -1 0 1 2 3 4 0 |
C | 0 1 2 0 0 1 2 |
G | -1 -1 0 1 2 3 4 |
T | -1 -1 -1 -1 -1 0 1 |
Based on this distance data, I can get the minimal impact factor for any slice.
My implementation in Python:
def solution(S, P, Q):
N = len(S)
M = len(P)
# impact factors
I = {'A': 1, 'C': 2, 'G': 3, 'T': 4}
# distance from current position to the nearest nucleotide
# for each nucleotide type (previous or current nucleotide are considered)
# e.g. current position is 'A' => the distance dist[0] = 0, index 0 for type A
# 'C' => the distance dist[1] = 0, index 1 for type C
pre_dists = [[-1]*N,[-1]*N,[-1]*N,[-1]*N]
# initial values
pre_dists[I[S[0]]-1][0] = 0
for i in range(1, N):
for t in range(4):
if pre_dists[t][i-1] >= 0:
# increase the distances
pre_dists[t][i] = pre_dists[t][i-1] + 1
# reset distance for current nucleotide type
pre_dists[I[S[i]]-1][i] = 0
# result keeper
res = [0]*M
for k in range(M):
p = P[k]
q = Q[k]
if pre_dists[0][q] >=0 and q - pre_dists[0][q] >= p:
res[k] = 1
elif pre_dists[1][q] >=0 and q - pre_dists[1][q] >= p:
res[k] = 2
elif pre_dists[2][q] >=0 and q - pre_dists[2][q] >= p:
res[k] = 3
else:
res[k] = 4
return res
I hope this helped. Thanks!