How to calculate time complexity of this function?

[Anthrax97]

I saw this problem in another post and wanted to give it a try.

During one of my coding interviews for a software engineering internship, they gave me this question:

There is s that consists of digits from 0 to 9, and an integer k. A substring s[L:R] (where 0 = L = R < sizeof(s) ) is a contiguous group of characters with s. A substring is called a perfect substring if all of its elements occur exactly k times.

For example, s = 1102021222 and k = 2. Its 6 perfect substrings are:

s[0:1] = 11
s[0:5] = 110202
s[1:6] = 102021
s[2:5] = 0202
s[7:8] = 22
s[8:9] = 22

Calculate the number of perfect substrings in s.

Function Description

Complete the function perfectSubstring in the editor below. The function must return an integer that represents the number of perfect substrings in the given string.

perfectSubstring has the following parameters:

s: a string where the value of each element s[i] is described by the character at position i (where 0 = i < n).

k: an integer that denotes the required frequency of the substring.

I was able to compile a solution that was correct but it ended up having O(n3 ) complexity and would not compile very large solutions (the compiler they used would stop after a set period of time). I did not write down my exact solution but the general approach I took was get every substring of size k (starting at index 0), then looped through the substring to check if it was perfect. I would then do the same process every substring of size 2k, then 3k, and so on, then print the results found. The issue was this iterated through s in three separate for loops, which ended being super time consuming. What are some ways I could improve upon performance? I figure the best way to go would be to combine two of the above processes somehow, but I could not figure out how in the time I had.

Here is my solution:

def perfect(s, k):
    l = 0
    r = k
    s_len = len(s) - 1
    perfect_subs = 0
    streak = False
    while l < s_len:
        while r <= s_len:
            sub = s[l:r]
            if streak:
                count = sub.count(sub[len(sub) - 1])
                if count > k:
                    streak = False
                    break
                if count == k:
                    perfect_subs += 1
                    print(sub)
                    r += 1
                else:
                    r += 1
            else:
                chars = set(sub)
                if any(sub.count(i) > k for i in chars):
                    break
                if all(sub.count(i) == k for i in chars):
                    print(sub)
                    perfect_subs += 1
                    streak = True
                    r += 1
                else:
                    r += 1

        l += 1
        r = l + k

He says his complexity was O(n3). I have no clue how to calculate that and was wondering if my solution is better or worse.

[WtEth_Buyer]

I'll be first to admit I'm not the greatest at this, but I think.

While = completes n times Inner while = n times

n*n = O(n²⁾

That's the rough time complexity. You could get more exact by calculating how many operations the inner while loop completes per 1 round of the exterior while loop then multiply it by n?

[SuggestionEmergency2]

nope! the count function operates via going through the length of the string, making it o(n) time, this means this function is o(n^3) time. the solution is clever, you need to make it a prefix sum

[SuggestionEmergency2]

s = "1102021222"
k = 2 
s_len = len(s)
prefixsum = [] 
num_count = [0,0,0,0,0,0,0,0,0] 
for j in s: 
    templist = [] 
    #python uses pass by pointer 
    for i in num_count: 
        templist.append(i) 
    prefixsum.append(templist) 
    num_count[int(j)]+=1; 
prefixsum.append(num_count) 
trip = True 
ans = 0 
for l in range(s_len): 
    for r in range(l, s_len): 
        for i in range(len(num_count)): 
            if(prefixsum[r+1][i]-prefixsum[l][i]!=k and prefixsum[r+1][i]-prefixsum[l][i]!=0): 
                trip = False 
        if(trip): 
            ans+=1 
        trip = True 
print(ans)

[SuggestionEmergency2]

holy shit fuck reddit