Print the longest alphabetical substring using Python and for ties, print the first substring

Question

Assume s is a string of lower case characters. Write a program that prints the longest substring of s in which the letters occur in alphabetical order.

For example, if s = 'azcbobobegghakl', then your program should print

Longest substring in alphabetical order is: beggh

In the case of ties, print the first substring. For example, if s = 'abcbcd', then your program should print

Longest substring in alphabetical order is: abc

Here's the code I found. How do I implement the latter condition in the question given above regarding ties?

    *s = raw_input('provide string: ')
    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('Longest substring in alphabetical order is: '+(''.join(final)))*

Answer 1

I'd approach the problem the following way:

• Let's define two strings: The current string of increasing letters and the currently longest string.
• Both strings are initialized with the first letter. (This way we can always read their last letter.)
• Then we iterate over the input string s (starting with the second character).
• If the current character c fulfills the requirement c >= current[-1], we add it to the current solution.
• We possibly store the current string as longest.
• If c does not fulfill the ordering requirement, we start with a new solution current = c.
• Finally, we print the longest string.

s = "azcbobobegghakl"
longest = s[0]
current = s[0]
for c in s[1:]:
    if c >= current[-1]:
        current += c
        if len(current) > len(longest):
            longest = current
    else:
        current = c
print "Longest substring in alphabetical order is:", longest

---

How to fix your code wrt. the mentioned condition:

Use > instead of >= in the comparison len(result) >= len(final), i.e. only update the final solution if it is longer, but not if it has the same length.

---

Considering Dylans comment

You're right. I updated both code and description to correctly handle the case when s ends with the longest alphabetical substring. (Moving else: two lines down was sufficient.)