What is the time complexity of this python function which includes slice operations?

I am learning python slice operations and I decided to write a simple function that iterates through a string with a window of size k and adds the window to the dictionary along with its frequency. So for example if the string input is "abab" and k is 2, the dictionary will contain "ab:2" and "ba:1".

I am confused what will be the time complexity of this function:

In the code, s is input string and k is window size.

def test_func(s, k):
    d = {}
    for i in range(len(s) - k + 1):
        sub_str = s[i:i+k]
        if sub_str in d:
            d[sub_str] += 1
        else:
            d[sub_str] = 1
    return d

I am thinking that time complexity of it will be O(n * k) and space complexity of it will be O(n) where n is size of list and k is size of window but I am not sure if it is right. Can you please review the function and let me know if my analysis is correct? Thank you!

>Solution :

Time and space should both be O(n*k).

Looking up a dictionary key of size k is O(k) because you have to hash k, which requires reading all the characters of k. While we often treat dictionary and set lookup as amortized constant time, I don’t think we can use that simplification when the dictionary key size is one of the parameters.

Since you do these lookups O(n) times, the time complexity is O(n*k).

Since all the keys have to be stored in the dictionary, and the worst case is that there are no duplicate slices, the dictionary may have to contain n*k keys.