# Finding the longest substring in alphabetical order

I wrote code in Python that takes a string s as input and determines the longest substring of s that’s in alphabetical order. In the case where there are two strings of the same length, code outputs the first one.

I'm a beginner with 1.5 weeks of experience and wrote both versions myself. Which one is better, and why?

## Version 1

def alphacheck(x):
'''This function checks if a given string is in Alphabetical order'''

# Creating a variable to allow me to efficiently index a string of any length
i = len(x) - 1
# Using a recursive formula and checking for the base case when the string is of less than one character
if len(x) <= 1:
return True
# This the recursive portion of the formula
else:
# This code checks if the last two characters are in alphabetical order
# By utilizing the property that the letters of the alphabet increase in "value" according to python
if x[i - 1] <= x[i]:
# I remove the last letter of the string to reduce the problem size
x = x[:i]
# I then repeat this on the smaller string until it reaches the base case or
# Finds out the string is not in alphabetical order and returns False
return alphacheck(x)
else:
return False

# The base list that i'll be editing
list1 = []
s = 'hlqrjqbjiwedjzzw'
#use i to determine the number of times i'll run the loop
i = int(len(s)+1)
#use u to change the size of my slice of the string
u = 0
itersLeft = i
# counter used to slice the string by picking the 1st element then the 2nd then 3rd then...
# then picking the 1st element and the 2nd element together then picking the 2nd element and the 3rd element together then....
counter = 0
while u <= i:
while itersLeft > 0:
#this is the code that slices up the string according the way outlined in earlier comments
x = s[counter-1:counter+u ]
list1.append(x)
itersLeft -= 1
counter += 1
#I change the value of u because that's what decides how big my slices are if u is 0 the slices are length 0 if u is 1 slices are lenght 1 and so on
u += 1
itersLeft = i
counter = 0
del list1

#This removes duplicates in the list by scanning the first list for elements and adding them to the second (empty)list if theyre not already in the secodn     list
list2 = []
numMatch = 0
for e1 in list1:
if e1 in list2:
#This numMatch variable is used just as a place holder since it's the else condition i need not the if
numMatch += 1
else:
list2.append(e1)
list3 = []
for e in list2:
if alphacheck(e) == True:
list3.append(e)
list4 = list3[:]
for e in list3:
if len(e) < len(list3[len(list3)-1]):
list4.remove(e)
print(list1)
print(list2)
print(list3)
print(list4)
print('Longest substring in alphabetical order is: ' + list4 )


## Version 2

def alphacheck(x):
'''This function checks if a given string is in Alphabetical order'''

# Creating a variable to allow me to efficiently index a string of any length
i = len(x) - 1
# Using a recursive formula and checking for the base case when the string is of less than one character
if len(x) <= 1:
return True
# This the recursive portion of the formula
else:
# This code checks if the last two characters are in alphabetical order
# By utilizing the property that the letters of the alphabet increase in "value" accroding to python
if x[i - 1] <= x[i]:
# I remove the last letter of the string to reduce the probelm size
x = x[:i]
# I then repeat this on the smaller string until it reaches the base case or
# Finds out the string is not in alphabetical order and returns False
return alphacheck(x)
else:
return False
lastr = ''
s = 'hlqrjqbjiwedjzzw'
#use i to determine the number of times i'll run the loop
i = int(len(s)+1)
#use u to change the size of my slice of the string
u = 0
itersLeft = i
# counter used to slice the string by picking the 1st element then the 2nd then 3rd then...
# then picking the 1st element and the 2nd element together then picking the 2nd element and the 3rd element together then....
counter = 0
while u <= i:
while itersLeft > 0:
#this is the code that slices up the string according the way outlined in earlier comments
x = s[counter-1:counter+u ]
if alphacheck(x) == True:
if len(x) > len(lastr):
lastr = x
itersLeft -= 1
counter += 1
#I change the value of u because that's what decides how big my slices are if u is 0 the slices are length 0 if u is 1 slices are lenght 1 and so on
u += 1
itersLeft = i
counter = 0
print('Longest substring in alphabetical order is: ' + lastr )


Neither are that good. Both suffer from the nested loops.

while u <= i:
while itersLeft > 0:
...
itersLeft = i


This means that the algorithm suddenly has a $O(n^2)$ time complexity. How many times do you run the code in while u <= i? That's i amount of times. In this you have the loop while itersLeft > 0, this runs i - itersLeft amount of times. And so you this runs $\Sigma_{\text{itersLeft}=0}^i(i - \text{itersLeft})$ amount of times. Which is the same as $\frac{1}{2}i(i + 1)$. And so we can simplify that to just $i^2$, and so it runs roughly $O(n^2)$ amount of times.

Instead I'd come at this to try to minimise the amount of loops. Preferably you should have one loop. To force this I'd use for item in string. After this we should aim to make all the substrings.

Looking at alphacheck we know that it's a new substring if prev > item. And so we'll want to add the previous substring to a new list when this happens. And so we should have the code:

def ordered_substrings(string):
substrings = []
prev = None
for item in string:
if prev is not None and prev > item:
substrings.append(...)
prev = item
return substrings


So, now we need to figure out what to add to substrings list. To do this is the hardest part of this algorithm. You need to create the substring which is all the items from the end of the last. If we make a new list to hold the creation of this substring and add to it each loop we can end up with:

def ordered_substrings(string):
substrings = []
substring = []
prev = None
for item in string:
if prev is not None and prev > item:
substrings.append(''.join(substring))
substring.append(item)
prev = item
return substrings


Running this on 'abcabca' results in ['abc', 'abcabc']. This shows two problems, it doesn't add the last substring. And we're adding old substrings. To fix these should be relatively simple now, when we add the substring to substrings, we need to reset it. and at the end we need to add to substrings. Resulting in:

def ordered_substrings(string):
substrings = []
substring = []
prev = None
for item in string:
if prev is not None and prev > item:
substrings.append(''.join(substring))
substring = []
substring.append(item)
prev = item
substrings.append(''.join(substring))
return substrings


To then further improve these I'd make the function a generator, which functions like range. But can allow you to reduce the amount of memory used. All you need to do is remove substrings, and change substrings.append to yield.

def ordered_substrings(string):
substrings = []
substring = []
prev = None
for item in string:
if prev is not None and prev > item:
yield ''.join(substring)
substring = []
substring.append(item)
prev = item
yield ''.join(substring)


And finally to use it, you can use max with the key keyword as len.

>>> max(ordered_substrings('abcabca'), key=len)
'abc'

• Nice way to decompose the problem into a max() and an ordered_substrings() function. – 200_success Sep 20 '16 at 2:54

“Better code” is asking for an opinion, as there is no objective measure of “better”. My initial, flippant, answer is that the one with 44 lines is better than the one with 67, since it gets the same job done in fewer lines, making it easier to read. (This is what I said to this question on Quora. Since this site is explicitly a code-review site, the philosophy of "better code" may be out of place. I'm sure the regular denizens of this stack exchange site will let me know if this is out of place).

This is not completely trivial (shorter = better). What is important is that computer languages are tools not just for instructing a computer, but also with communicating with other programmers. Computer programs are not static, and you will, in your career as a programmer, find yourself reading code written by others a lot more often than writing new code from scratch. As such, one of the most important needs of “good” code is readability.

Kent Beck highlighted Four rules of Software Design which might be useful to keep in mind. Martin Fowler's description of those four rules are:

• Passes the tests (i.e., it works as expected)
• Reveals intention
• No duplication
• Fewest elements

The last three rules are really rules for readability: You can read it and see what it does, it doesn’t do things more than once, and it’s simple and clear.

You have 1.5 weeks of experience. It isn’t expected that your code is readable or “good”, but it is something you should strive for for your entire career. Professional programmers struggle on this their entire careers, and it is not uncommon for a professional to have to fix a bug in code that hasn’t been touched in 6 months to a year, complain about how crappy it is, and then find that they wrote it. Improving is a continuous process.

With that in mind, let’s look at the code. I will try at first to compare the two versions, then give you ideas on how to improve it.

First, you have defined a recursive function to determine if a string is in alphabetical order, alphacheck(x)

This is identical in the long version, so it doesn’t make either version better or worse.

Next, you have a section which (presumably) differs between versions, because of length.

Now I would definitely say I would rather edit the shorter version that the longer version. Both versions have a loop which (I assume, without close analysis) finds all substrings of s.

The short version checks to see if the substring is alphabetical, and if it is, if it’s longer than any seen before. Since after processing all the substrings, the longest, alphabetical substring has already been found and stored, all that’s needed is to print it.

The longer version generates a list of substrings (list1), removes duplicates to get list2, collects just the ones which are alphabetic to get list3, then finds the longest substrings list4, then returns the first one.

The short version expresses its intent better (it took me a few read-throughs to understand the long version). Both versions have opaque names (what is u? i? Why are they named that?), but the longer version has more, especially list1, list2,list3,list4.

One place where intent-revealing could be helped in the longer version is the expression len(list3[len(list3) -1]). It is a bit complex, and it’s uncertain if it ever changes. I also think it’s a potential location of a bug (it looks like you are removing strings from list3 that are shorter than the last string, but how do we know that the last string is the longest?

There is little obvious duplication in either. I’m sure there is some, probably in the form of repeated calculations of string lengths of the same string, but nothing jumps out.

When evaluating “fewest elements”, this is mainly in the form of looking for things which can be improved or simplified. Obviously, the longer version has more elements than the shorter version, but they are also doing different things. It is hard (using the language and style that you are using) to write the longer version using fewer “elements” than the shorter version, so it is unfair to say the shorter version has 5 variables while the longer version has 12 and say simply from that that the shorter version is better.

But we can look at the longer version, and point out that you have three loops using the variables e, e1, e, and the structure is such that clearly you can use e for all three loops. Similarly, you have numMatches which even in your comments you acknowledge is superfluous, just there because you want the else branch of an if, and need something in the other branch. That’s an element that can be removed (if you knew how to invert the if (check out element not in array)).

I don’t see that sort of redundant elements in the shorter version. The itersLeft variable looks dubious, or at least poorly named, but I can’t obviously see how it can be removed.

So based on those measures, I’d say the strict answer to your question remains: Version 1 is “better” code.

Since you’ve essentially asked for a code review, I’ll continue with the other important part of a code review: how can it be made better? This is not intended to be an ego-busting exercise: I’m not saying “you write crappy code, here’s how a pro would do it”, I’m trying to give you advice on how you can take the code you’ve written and improve it. There are some programming disciplines where programmers will write dirty code, verify it works, then clean it immediately before anyone else sees it, all within minutes, all throughout the day.

So, taking your recursive alphacheck. Here are some small changes you can do:

• My preference is to push the declaration of variables to as close as their use as possible. Here, you immediately declare i = len(x) -1, but then don’t use it at all except in the else block of your main test. So I would tend to put the initialization of to within that else block, as close to where you use it as possible.
• i is a really crappy variable name in most cases. What does i represent here? It’s the index of the last character in the string. So I’d probably rename it as last_index or similar.
• Looking at the line x = x[:last_index], I’d be reminded of Python’s array slicing s[i:j], and the note that if either i or j is missing, gets a reasonable default (either 0 or len(s)), and if either i or j is negative, it is considered to be from the end of the list, not the beginning. So x = x[:last_index] can be replaced by x = x[:-1].
• Similarly, the if condition x[last_index-1] <= x[last_index] can be simplified to x[-2] <= x[-1].
• Which means that last_index is no longer being used, and can be deleted!
• This is sort of a style thing, but when I think of a recursive function, I also tend to think in a “functional” programming style, which eschews the reassignment of variables. That makes me somewhat leary of x = x[:-1], as it is reassigning x. It isn’t in a loop, where you have to change the condition of the loop, so I’d consider renaming the latter x, so it is shortened_string = x[:-1], and similarly change the next line to refer to the new variable.
• Better yet, since it is a simple expression, and it’s only used in one place, I’d definitely consider “inlining” it, to remove the variable entirely. That makes the return statement return alphacheck(x[:-1]).
• Another style thing is eliminating deep nesting. In your first “if” statement, the last thing that happens before the “else” is a return. Code will not continue after the return, which makes the else sort of redundant. I would eliminate the else, and remove a level of nesting in the process.
• I prefer to have the recursive call last. Right now, it isn’t, it’s embedded in an if block. So I would invert that if condition (and switch the two code blocks) to be x[-2] > x[-1], or x[-1] < x[-2], then I would remove the else as described above.

This gives a final code of

def alphacheck(x):
if len(x) <= 1: # Empty or single character strings are alphabetic
return True;
if x[-1] < x[-2]: # if last two characters are out of order, not alphabetic
return False;
return alphacheck(x[:-1]) # recursively check truncated string


I probably wouldn’t include the comments as redundant. Personally, I would probably be annoyed by the negative indices, and note that I can do the check and truncation from the beginning of the string instead, but that wouldn’t be improving your code; that would be changing your algorithm. I’m not trying to do that here.

The nine steps I described come with practice. To do them, you have to look for possible ways to improve it, and you have to see how to make those changes. If you notice, several of the steps were dependent on earlier steps, and the results of some of those steps vanished (I changed a variable name, then eliminated the variable, for instance). Improving your code this way is an iterative process of looking for small changes that can make things better.

I’ll leave improving your other two versions as an exercise for you.

One tip you might want to consider when you do: In the above example, I used the language feature that negative indices on arrays come from the end, not the beginning. This is a language feature you might not have known about. For the long-version, I suggest you look up Python array comprehensions as a language feature you might not have known about which may greatly help your code.

Version 2 is better in that it only keeps the best result seen so far. As a result, it doesn't need all this deduplication code in Version 1:

#This removes duplicates in the list by scanning the first list for elements and adding them to the second (empty)list if theyre not already in the secodn     list
list2 = []
numMatch = 0
for e1 in list1:
if e1 in list2:
#This numMatch variable is used just as a place holder since it's the else condition i need not the if
numMatch += 1
else:
list2.append(e1)
list3 = []
for e in list2:
if alphacheck(e) == True:
list3.append(e)
list4 = list3[:]
for e in list3:
if len(e) < len(list3[len(list3)-1]):
list4.remove(e)
print(list1)
print(list2)
print(list3)
print(list4)


However, both solutions are hugely inefficient.

Both functions have the same alphacheck() function in common. You already got a review of that code, with many excellent answers, such as this suggested solution. Note that your alphacheck(x) is $O(\left|x\right|^2)$, where $\left|x\right|$ is the length of its input. It should ideally be $O(\left|x\right|)$, but your x = x[:i] string slicing makes it do a lot of extra work.

You also got some criticism that your comments are too verbose — and I agree that the same criticism applies here. This comment in particular… I have no idea what you are trying to say:

# counter used to slice the string by picking the 1st element then the 2nd then 3rd then...
# then picking the 1st element and the 2nd element together then picking the 2nd element and the 3rd element together then....


Both algorithms work by checking all possible substrings of length 1, then all possible substrings of length 2, etc. Since your alphacheck(x) function is $O(\left|x\right|^2)$, your Version 2 is

$$O(1^2 + 2^2 + 3^2 + \ldots + \left|s\right|^2) = O(\left|s\right|^3)$$

If you revised alphacheck(x) to be $O(\left|x\right|)$ as it should be, then it would be

$$O(1 + 2 + 3 + \ldots + \left|s\right|) = O(\left|s\right|^2)$$

But you should be able to solve this problem in just one pass, comparing each letter with its neighbour. That would be $O(\left|s\right|)$. Here, I've used a namedtuple to help make it easier to manage four variables, but you could also write it with best_start, best_end, substring_start, substring_end as four separate variables.

from collections import namedtuple

def first_longest_asciibetical_substring(s):
Span = namedtuple('Span', 'start end')
best = substring = Span(0, 1 if s else 0)
for i in range(1, len(s)):
# This is actually an ASCIIbetical comparison, not alphabetical,
# since it doesn't mix upper- and lowercase.
if s[i - 1] > s[i]:
substring = Span(i, i + 1)
else:
substring = Span(substring.start, i + 1)
if substring.end - substring.start > best.end - best.start:
best = substring
return s[best.start : best.end]

• Nice answer, is ord(s[i - 1]) > ord(s[i]) the same as s[i - 1] > s[i]? Or am I missing something? – Peilonrayz Sep 20 '16 at 0:54
• @JoeWallis That was silly. I don't know why I added ord(…). I've removed them in Rev 3. – 200_success Sep 20 '16 at 2:35

I appreciate this is rather old now, but it all seems over complicated above - would something like this ( which makes only one pass ) not work?

length, start, stop, i = len(s), 0, 0, 0

while i < length:

j = i+1

while j < length and s[j] >= s[j-1]:
j += 1

if j - i > stop - start:
start, stop = i, j

i = j

print(s[start:stop])