A program that prints the longest substring of s in which the letters occur in alphabetical order

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

I have been working on a edX course, MITx: 6.00.1x Introduction to Computer Science and Programming Using Python. Encountering the problem mentioned above, I set out to write a piece of code which I found to be the most disgusting to date(excluding Project Euler draft code).

Note: s can be any input, but in my case, edX will automatically input a value for s, so I do not need to define s.

first=0
second=1
strang1=''
strang2=''
while second<len(s):
    if second>=len(s):
        break
    elif s[first]<=s[second]:
        strang1+=s[first:second+1]
        while second<=len(s):
            second+=1
            if second>=len(s):
                break
            elif s[second]>=strang1[-1]:
                strang1+=s[second]
                if len(strang1)>len(strang2):
                    strang2=strang1
            else:
                if len(strang1)>len(strang2):
                    strang2=strang1
                strang1=''
                first=second-1
                break
    else:
        if len(s[first])>len(strang2):
            strang2=s[first]
        first+=1
        second+=1
print("Longest substring in alphabetical order is:" + strang2)

The code can accurately take on any input(if defined) and output it accurately(according to the edX's test runs). I'm looking to make my code more efficient, any suggestions? I'll accept any, fancy newfangled functions or maybe a total rework, I don't mind.

Answer 1

You should put this code into a function so you are able to easily test and reuse it. Also make yourself familiar with the if __name__ == '__main__': guard.

Now, for your approach, you basically search for any substring in alphabetical order and, as you do, save the longest for future processing. You could split your code into several smaller functions to help you organize it. A generator of substrings in alphabetical order may be of a great benefit:

def alphabetical_substrings(word):
    current_sequence = []
    last_letter = ''

    for letter in word:
        if letter >= last_letter:
            current_sequence.append(letter)
        else:
            yield ''.join(current_sequence)
            current_sequence = []
        last_letter = letter

    if current_sequence:
        yield ''.join(current_sequence)

Then finding the longest is as simple as using the builtin max with a special key argument; it has the desired behaviour of returning the first value that matches the maximal criterion:

def longest_substring_in_alphabetical_order(word):
    return max(alphabetical_substrings(word), key=len)

Lastly the tests could look like:

if __name__ == '__main__':
    print(longest_substring_in_alphabetical_order('azcbobobegghakl'))

---

You can also simplify the writting of the generator using the pairwise recipe:

import itertools


def pairwise_letters(iterable):
    """Generate pairs of elements e_n, e_n+1 from iterable.

    It is assumed that iterable contains characters and the last
    pair will contain its last element and the empty string so as
    to break alphabetical ordering.
    """
    first, second = itertools.tee(iterable)
    next(second, None)
    yield from itertools.zip_longest(first, second, fillvalue='')


def alphabetical_substrings(word):
    """Generate the substrings of `word` that appear in alphabetical order"""
    current_sequence = []
    for letter, next_letter in pairwise_letters(word):
        current_sequence.append(letter)
        if letter > next_letter:
            yield ''.join(current_sequence)
            current_sequence.clear()


def longest_substring_in_alphabetical_order(word):
    return max(alphabetical_substrings(word), key=len)


if __name__ == '__main__':
    print(longest_substring_in_alphabetical_order('azcbobobegghakl'))

Answer 2

if second>=len(s):
    break

This is not necessary. You have just checked that in the loop condition.

---

first=0
second=1
strang1=''
strang2=''

Consider renaming these variables to say what they do more clearly. Even "begin" and "end" would be clearer than "first" and second, but do not be afraid of longer variable names.

As a rule of thumb, be wary of variable names which you have numbered. They often mean either that they do sufficiently the same thing and you could simplify the code by putting them in a list and looping, or they do not do the same thing and you should name them appropriately. (As is the case here)

---

strang1+=s[second]
if len(strang1)>len(strang2):

Constructing strings, especially one character at a time, is an expensive operation. You could do this more efficiently by just storing the location in the input string. You can compare sizes just by subtracting the start of that location from the end. At the end of the loop, you can assign the result in one go using s[start:end] notation.

---

Assume s is a string of lower case characters.

When you have assumptions like this, it is generally prudent to check them. Coding challenges won't tend to require it. When you have a larger code base and are trying to work out where something went wrong, you'll thank your past self if the first thing that was given input it wasn't designed for is screaming about it so you know where to look.

Answer 3

You could also use regular expressions to search for the string in question:

import re, string

# Regex looks like 'a*b*c*...z*'
alphabetical_order = re.compile('*'.join(string.ascii_lowercase) + '*')

longest_match = max(alphabetical_order.findall(some_string), key=len)

An example run:

In [1]: alphabetical_order.findall('abcbcdcdef')
Out[1]: ['abc', 'bcd', 'cdef', '']

In [2]: max(_, key=len)
Out[2]: 'cdef'

In [3]: max(alphabetical_order.findall('abcbcd'), key=len)
Out[3]: 'abc'

Pros: Very little code required; easy to change "alphabetical order"; strictly-defined alphabet, so no mistakes in case of unexpected input; trivial support for unicode and case-insensitivity.

Cons: Cryptic code; not faster than @MathiasEttinger's solution, unless you make it case-sensitive (in which case it's slightly faster for the same functionality).

Answer 4

    while second<=len(s):
        second+=1
        if second>=len(s):
            break

These four lines can be replace by for second in range(second+1, len(s)):.