What is the time complexity of suggested solution?

Question

This is the solution for the following problem: Given two strings s and t of length N, find the maximum number of possible matching pairs in strings s and t after swapping exactly two characters within s. A swap is switching s[i] and s[j], where s[i] and s[j] denotes the character that is present at the ith and jth index of s, respectively. The matching pairs of the two strings are defined as the number of indices for which s[i] and t[i] are equal. Note: This means you must swap two characters at different indices.

What is the time complexity of this?

s = "abcd"
t = "adcb"

tl = list(t)
pairs = []

for i in range(len(list(s))):
    window = 1
    j = i + window 
    
    while j < len(s):
        sl = list(s)
        sl[i], sl[j] = sl[j], sl[i]

        ds = {sl[k]: k for k in range(len(sl))}
        dt = {tl[k]: k for k in range(len(tl))}
        
        pairs.append(len(ds.items() & dt.items()))
        j += 1
        
max(pairs)

Answer 1

The complexity of your algorithm is O(N³).

The maximum depth of your nested loops through your arrays is 3. We can ignore the series of loops inside the while in this case to calculate the complexity. (The complexity is O(NN3N) which is equivalent to O(N³))

There is a good explanation on how to compute the complexity here