0

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)
AcK
  • 2,063
  • 2
  • 20
  • 27
user2645029
  • 63
  • 1
  • 9
  • What did you find when you measured it? – mkrieger1 Apr 29 '22 at 07:26
  • My thinking was the first for loop is O(N), while loop is O(N), ds={..}, dt={..} are both O(N), pairs.append(...) is O(N) as well so that is O(N^5) in total? – user2645029 Apr 29 '22 at 09:24
  • Why O(N⁵) ? Following your reasonning shouldn't it be O(N³) ? – Gaston Apr 29 '22 at 09:29
  • Because there are 5 * O(N) loops in total? – user2645029 Apr 29 '22 at 09:35
  • 1
    You're right, there are 5 loops, but only 3 loops of loops. Meaning that the complexity is : O(N*N*(N+N+N)) which is equivalent to O(N³) – Gaston Apr 29 '22 at 09:40
  • When you say 3 loops of loops, which ones are you referring to? And why not take into account others? – user2645029 Apr 29 '22 at 09:46
  • I am referring to the forloop, the whileloop and all things inside the while. There are 3 nested loops, with some loops inside the while. The complexity is then O(N*N*3N) but we always throw the constants when calculating the complexity. There's a very clear explanation of big O notation [here](https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) – Gaston Apr 29 '22 at 09:54

1 Answers1

0

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

Gaston
  • 185
  • 7
  • Thanks, this is what made me understand, maybe add that to your answer too: "The complexity is then O(N*N*3N) " – user2645029 Apr 29 '22 at 10:01