11
\$\begingroup\$

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.

\$\endgroup\$

4 Answers 4

11
\$\begingroup\$

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'))
\$\endgroup\$
3
  • 1
    \$\begingroup\$ I used to take 6.00.1x and I think that this answer is out of scope of the edX course the OP was taking. Useful nevertheless. \$\endgroup\$
    – svavil
    May 12, 2018 at 0:14
  • 1
    \$\begingroup\$ @svavil I agree but itertools is flippin cool, this is pretty useful to know, as well as if name == 'main':, confusing to me at first, but with a little time I should be able to use these functions in other projects. \$\endgroup\$ May 12, 2018 at 2:07
  • \$\begingroup\$ Found a bug in the code. If s = 'bylwgagog', the program will output by instead of ago. Should add current_sequence.append(letter) in the else section too. \$\endgroup\$
    – Gejun
    Feb 2, 2021 at 16:40
11
\$\begingroup\$
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.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks for the heads up and all the tips! I will be more clear in my variable names, a bad habit of mine due to how lazy I am as well as I feel the lack of need of them with the relatively short amount of lines I have to write, but it is still a bad habit nonetheless. \$\endgroup\$ May 12, 2018 at 2:10
4
\$\begingroup\$

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).

\$\endgroup\$
3
  • \$\begingroup\$ re.compile('*'.join(alphabet))? \$\endgroup\$ May 11, 2018 at 19:37
  • \$\begingroup\$ @MathiasEttinger you need the trailing '*', so it'd need to be re.compile('*'.join(alphabet) + '*') which looks a bit less clear to me (but I'm also overly fond of comprehensions and format strings, so others might find that more clear) \$\endgroup\$
    – scnerd
    May 11, 2018 at 20:29
  • \$\begingroup\$ right, or even define the string manually with the stars since you are redefining string.ascii_lowercase anyway. \$\endgroup\$ May 11, 2018 at 20:33
3
\$\begingroup\$
    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)):.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.