Codeforces Round #656 (Div. 3) QD. a-Good String solution Compare

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()[submission:87157593]↵
↵
↵
### **Solution Giving TLE**↵
[submission:87147602]↵
↵
        ↵