finding the longest substring of letters in alphab

Question

When executing my code for the given task, I keep getting the longest string plus the next letter in the iteration. For example, if I use

s = 'azcbobobegghakl' 

I will get "beggha" as the longest string, when the answer is supposed to be "beggh". This same bug occurs for all strings of random letters I tried.

I have figured out that the extra letter gets added on after the "result += letters" statement, but I'm not sure how to fix it. Here is my code:

s = 'azcbobobegghakl'
result = []
final = []
for letters in s:
    result += letters
    if result == sorted(result) and len(result) >= len(final):
        final=result
    elif result != sorted(result): 
        result = [result[len(result)-1]]
print "".join(final)

Answer 1

The problem here is that result and final point to the same list. You are probably thinking that += will create a new list when you issue result += letters, but it won't:

>>> x = [1,2]
>>> y = x
>>> x += [3]
>>> x
[1, 2, 3]
>>> y
[1, 2, 3]
>>> x is y
True

However, when you use x = x + [3]:

>>> x = [1,2]
>>> y = x
>>> x = x + [3]
>>> x
[1, 2, 3]
>>> y
[1, 2]
>>> x is y
False

For an explanation of this behavior, see this question. This is what's happening in your for loop (edit: of your original code) when letters is the last a character in your string:

1. at the beginning, final and result both point to ['b', 'e', 'g', 'g', 'h'].
2. after result += 'a' final and result both point to ['b', 'e', 'g', 'g', 'h', 'a'].
3. now the elif block is entered and result will point to a new list ['a'], while final still points to ['b', 'e', 'g', 'g', 'h', 'a'].
4. final will never be updated again after this

Hence, your original code (before you edited it) can be fixed by changing

result += letters

to

result = result + [letters]:

s = 'azcbobobegghakl'
result = []
final = []
for letters in s:
    result = result + [letters]        
    if result == sorted(result) and len(result) >= len(final):
        final=result            
    elif result != sorted(result):
        result = [result[len(result)-1]]        

print(final)

Answer 2

You've got a couple items to address. The first is that when you use...

final = result

This is not just assigning the values in result to final. It points the variable 'final' to the memory address containing the list that 'result' is also pointing to. So then if result is changed, so is final. To assign the values in result, use...

final = result[:]

which will give you the values of a slice of the list from beginning to end. Or you can use...

final = list(result)

After that change, you'll need to remove the length comparison in your elif statement.

Edited code:

s = 'azcbobobegghakl'

result = []
final = []

for letters in s:
    result += letters
    if result == sorted(result) and len(result) >= len(final):
        final = list(result)
    elif result != sorted(result):
        result = [result[len(result)-1]]
print "".join(final)