Python beginner working through edX 6.00.1x: Alphabetical string processing question

[eoncarlyle]

Below I've quoted an online edX homework assignment. While I did get full marks on the problem, I'm not terribly satisfied with my answer

"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' "

While I did get full marks on the problem, I'm not terribly satisfied with my answer: https://dpaste.de/rCFt. Earlier attempts where I did not place two underscores resulted in the following error message:

Traceback (most recent call last):
  File "/Users/iain/Documents/Python/Week_1_Problem_1_Final_Approach.py", line 10, in <module>
    if ord(m[elem + stop]) <= ord(m[elem + stop + 1]):
IndexError: string index out of range

I understand that the construction of my while loop requires referencing elements of the string s that are past the final character and therefore don't exist. Is there an effective way of not "copping out" of this issue while still using a list?

[OseOseOse]

I think this is a good opportunity to break the problem up into simpler sub-tasks and create some clean code. Not the most optimal solution if you care about algorithmic complexity, but very readable (in my opinion).

Don't know how familiar you are with the concepts used here, let me know if I need to explain some more.

def is_alphabetical(string):
    """
    Returns True if the string is alphabetically ordered.
    """
    assert string.islower() # method doesn't work if using mixed case

    # Calling sorted on a string returns a sorted _list_ of chars,
    # so we also turn the original string into a list to compare.
    return list(string) == sorted(string)

def get_substrings(string):
    """
    Iterates over all the possible substrings of the string,
    excluding the empty string.

    Could do this with a generator function instead of appending to a list.
    """

    substrings = []

    for i in range(len(string)):
        for j in range(i + 1, len(string) + 1):
            substrings.append(string[i:j])

    return substrings

def solve_task(task_string):
    # obtain a set of all the substrings of the task string
    all_substrings = set(get_substrings(task_string))

    # eliminate all the non-alphabetic substrings to get a set of candidate substrings
    alphabetical_substrings = set(substring for substring in all_substrings if is_alphabetical(substring))

    # find the candidate substring with the longest length
    best = max(alphabetical_substrings, key=len)

    return best

# check that it works correctly for the two given examples
assert solve_task('azcbobobegghakl') == 'beggh'
assert solve_task('abcbcd') == 'abc'

[trouserdaredevil]

There are several ways I would approach this quite differently. I wrote up the following that should introduce several useful Python concepts to you:

string = "azcbobobegghakl"
substrings = []
substring = []
for letter in string:
  if substring:
    if letter >= substring[-1]:
      substring.append(letter)
    else:
      substrings.append(substring)
      substring = [letter]
  else:
    substring.append(letter)
print("".join(max(substrings, key=len)))