How to Find the Longest Substring in Alphabetical Order in Python

The challenge

Find the longest substring in alphabetical order.

Example:

the longest alphabetical substring in "asdfaaaabbbbcttavvfffffdf" is "aaaabbbbctt".

Overview:

There are tests with strings up to 10 000 characters long so your code will need to be efficient.

The input will only consist of lowercase characters and will be at least one letter long.

If there are multiple solutions, return the one that appears first.

The solution in Python

Option 1:

import re reg = re.compile('a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z*') def longest(s): return max(reg.findall(s), key=len)
Code language: Python (python)

Option 2:

def longest(s): k = [] for i in range(len(s)-1): if s[i] <= s[i+1]: k.append(s[i]) else: k.append(s[i]) k.append(' ') k += s[-1] return max(''.join(k).split(), key=len)
Code language: Python (python)

Option 3:

def longest(s): chunks = [] for c in s: if chunks and chunks[-1][-1] <= c: chunks[-1] += c else: chunks.append(c) return max(chunks, key=len)
Code language: Python (python)

Test cases to validate our solution

test.assert_equals(longest('asd'), 'as') test.assert_equals(longest('nab'), 'ab') test.assert_equals(longest('abcdeapbcdef'), 'abcde') test.assert_equals(longest('asdfaaaabbbbcttavvfffffdf'), 'aaaabbbbctt') test.assert_equals(longest('asdfbyfgiklag'), 'fgikl') test.assert_equals(longest('z'), 'z') test.assert_equals(longest('zyba'), 'z')
Code language: Python (python)
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments