Mysterious output while recursing in python

Question

I'm kinda new here and I just know the meaning of a recursion function but something strange happens when I try to excute it.

I'm trying to solve a leetcode problem of "Longest Substring Without Repeating Characters". In short they want to output the length of the longest continous substring in a provided string without any repeating charachters.

Here's my code

def getmax(s):
    having = []
    length = 0
    highest = [0]
    
    for i in  s:
        if i not in having:

            length +=1
            having.append(i)
            
            print(having)
            
            highest.append(length)
            
            print(length)


            if s.index(i) == len(s)-1:
                print("DONE",max(highest))
                return max(highest)
   
        else:
            new_s = s[s.index(i)+1:]
            getmax(new_s)

            
print(getmax("ckilbkd"))

So, my algorithm for this is to start incrementng the length, adding the length to a list to find the maximum later on, untill finding a repeated character. If this happens, the function is called again with a new string such that if for example s = dvdf the new_s string is only vdf. and if s = ckilbkd , new_s will be ilbkd. I can't explain it clearly but it removes anything before the original repeated character.

After that i run the function again on the new shorter string till finding a repated charachter. If not and the new_s is finally all unique i want to return the maximum value of the list that i have been appending the lengths in so far. And to know that the string is finished I added the condition if s.index(i) == len(s)-1:to see if it's the last charachter in the string or not.

For the string "ckilbkd" output should be 5 "ilbkd". During my debugging process I found this:

['c'] 
1                          #starts with the c, length is now 1
['c', 'k']
2                          #unrepeated charcter length is 2 
['c', 'k', 'i']
3                          #unrepeated charcter length is 3
['c', 'k', 'i', 'l']
4                           #unrepeated charcter length is 4
['c', 'k', 'i', 'l', 'b']
5                           #unrepeated charcter length is 5
['i']
1                           #repeated charachter found, starts over with new_s = ilbkd, length is now 1
['i', 'l']
2                           #unrepeated charcter length is 2 
['i', 'l', 'b']
3                           #unrepeated charcter length is 3 
['i', 'l', 'b', 'k']
4                           #unrepeated charcter length is 4 
['i', 'l', 'b', 'k', 'd']
5                           #unrepeated charcter length is 5
DONE 5                      #Should stop HERE
['c', 'k', 'i', 'l', 'b', 'd']
6                           #Dont understand what's happening here
DONE 6
6

It's working fine till the line after DONE 5.
then the list having is now a mess that i can't understand at all.

I'm trying to understand why is this happening more than to actually solve the problem, would appreciate if someone could explain what's happening without actually spoiling the solution.

Ignatius Reilly · Accepted Answer · 2023-06-02T00:25:16.227

You forgot the return in the recursive case. So, the call to getmax(new_s) get's the return of the base case, max(highest), but it doesn't do anything about it. And the for loop continues...

Why does the function returns a truncated version of the whole string?

The reason is simple: Because you don't have a return (or a break) in the else block, the for loop is not broken and keeps adding letters to having. However, the repeated letter that triggered the execution of the else block is not added.

Basically, your functions sees 'c' -> 'c' is not in having -> appends 'c' to having.
'k' -> 'k' is not in having -> appends 'k' to having ... and so on until it reaches the second 'k'.
Second 'k' is in having -> doesn't append it, calls getmax with new_s, but it doesn't matter because it does nothing with the output of that call. So it keeps looping and now it sees 'd', which is not in having, and appends it. At the end you get the whole string except for the second 'k' that wasn't appended.

Well, return(getmax(new_s)) worked so Thanks! but one last thing to get all the stuff in my head, what part of the for loop exactly did output ['c', 'k', 'i', 'l', 'b', 'd'], like this list is nothing like the one before it. — Abdulrhman Shaheen, Jun 01 '23 at 12:46

Mysterious output while recursing in python

1 Answers1

Why does the function returns a truncated version of the whole string?