Can't pass test case#4 and onwards... Any help optimizing the following python 3?

newS=s[left:right+1]

sub=[newS[i:i+j] for j in range(1,len(newS)+1) for i in range(len(newS)-j+1)]

print(len(set(sub)))

Since this is a discussion, I will just put here: The main problem is counting unique substrings. This is not done by simple combinatorics (I know the formulas and it doesn't work here). It is also not done by double for-loops to add all possible strings to a set/list (less repeated ones), as that has to be done in O(n^2).

This problem has to be done in O(n). I don't have the exact solution, but I'm guessing it is probably done by a suffix tree. And one of the only ways to build a suffix tree in O(n) time complexity is using Ukkonen's algorithm. It's not as simple as you think. Google it and find out. Most of the codes posted here (as are those i'm able to come up with) have too high a time complexity to past the latter cases. The algorithm is named for a reason. And this is expert for a reason.

I have yet to start writing code on this, but I'm thinking that it might be good to build a suffix array augmented with LCP array. I know that they can be used to quickly count the number of distinct substrings of a given string. But I'm still strugling to figure out how to deal with multiple queries, quickly counting substrings of a substring?

New to python here thats why the lengthy code:

def countSubstrings(s, queries):
    endresult = []
    for i in range(len(queries)):
        
        left = queries[i][0]
        right = queries[i][1]+1
        sub = s[left:right]
        a,r,k = '',[],[]
        if len(sub) == 1 or len(sub) == 0:
            endresult += [len(sub)]
            continue
        
        else:
            for i in sub:
                if i not in r:
                    r += [i] #all unique letters added to list
            for i in range(len(sub)):
                for j in range(i,len(sub)):
                    a += sub[j]
                    r += [a]
                a = ''
            for i in range(len(sub)):
                for j in range(len(sub)-1,i+1,-1):
                    a = sub[j]
                    r += [a]
                a = ''
        
        for i in r:
            if i not in k:
                k += [i]
        endresult += [len(k)]
    return endresult
        

Python 3 runtime error

def countSubstrings(s, queries):
    # Write your code here
    arr = []
    st = ""
    for i in queries:
        st = s[i[0] : i[1] + 1]
        result = set()
    
        for i in range(len(st) + 1):
            for j in range(i + 1 , len(st) + 1):
                result.add(st[i : j])
        
        arr.append(len(result))
    
    return arr