Can anyone tell why second solution gave TLE

Accepted Solution

def goodString(s, len, charCode): h, char = len // 2, chr(charCode) if len == 1: if s == char: return 0 else: return 1 s1, s2 = s[:h], s[h:] a1 = h — s1.count(char) + goodString(s2, h, charCode + 1) a2 = h — s2.count(char) + goodString(s1, h, charCode + 1)

return min(a1, a2)

T = int(input()) for _ in range(T): N = int(input()) A = input() ans = goodString(A, N, 97) print(ans)

Solution Giving TLE

def goodC(s,c,preSum,l,r): #print(l,r,c) if(l==r): if(c==s[l]): return 0 else: return 1

m=(l+r)//2
smid=(r-l+1)//2
if(l>0):
    sm=preSum[m][ord(c)-ord('a')]-preSum[l-1][ord(c)-ord('a')]
else:
    sm=preSum[m][ord(c)-ord('a')]
sr=preSum[r][ord(c)-ord('a')]-preSum[m][ord(c)-ord('a')]
#print(sm,"=",smid-sm,sr,"=",smid-sr)
return min( goodC(s,chr(ord(c)+1),preSum,l,m)+smid-sr, smid-sm+goodC(s,chr(ord(c)+1),preSum,m+1,r))

def main(): n=int(input()) s=str(input()) preSum=[[0 for _ in range(26)] for _ in range(len(s))] for i in range(0,len(s)): preSum[i][ord(s[i])-ord('a')]=1 for i in range(1,len(s)): for j in range(26): preSum[i][j]+=preSum[i-1][j]

#print(preSum)
print(goodC(s,'a',preSum,0,len(s)-1))

for _ in range(int(input())): main()