string - Bear and Steady gene - code optimisation(python) -
i have string containing a,g,c , t(length n). string steady if contains equal number of a,g,c , t(each n/4 times). need find minimum length of substring when replaced makes steady. https://www.hackerrank.com/challenges/bear-and-steady-gene
suppose s1='aagaagaa' since n=8 ideally should have 2 a's, 2 t's, 2 g's , 2 c's. has excess a's 4. hence need substring contains @ least 4 a's. start taking 4 character substring left , if not found increase mnum(variable) 1(ie 5 variable substrings , on) aagaa answer. but it's slow.
collections import counter import sys n=int(input()) #length of string s1=input() s=counter(s1) le=int(n/4) #ideal length of each element comp={'a':le,'g':le,'c':le,'t':le} #dictionary containing equal number of elements s.subtract(comp) #finding how each element ('a','g'...) in excess or loss a=[] b=[] x in s.values(): #storing frequency(s.values--[4,2]) of elements in excess if(x>0): a.append(x) x in s.keys(): #storing corresponding elements(s.keys--['a','g']) if(s[x]>0): b.append(x) mnum=sum(a) #minimum substring length start if(mnum==0): print(0) sys.exit flag=0 while(mnum<=n): #(when length 4 substring a's , g's not found increasing 5 , on) in range(n-mnum+1): #finding substrings length mnum in s1 j in range(len(a)): #checking if of excess elements present if(s1[i:i+mnum].count(b[j])==a[j]): flag=1 else: flag=0 if(flag==1): print(mnum) sys.exit() mnum+=1
here's 1 solution limited testing done. should give ideas on how improve code.
from collections import counter import sys import math n = int(input()) s1 = input() s = counter(s1) if all(e <= n/4 e in s.values()): print(0) sys.exit(0) result = math.inf out = 0 mnum in range(n): s[s1[mnum]] -= 1 while all(e <= n/4 e in s.values()) , out <= mnum: result = min(result, mnum - out + 1) s[s1[out]] += 1 out += 1 print(result) 