Find the longest substring in alphabetical order

s = 'cyqfjhcclkbxpbojgkar'
r = ''
c = ''
for char in s:
    if (c == ''):
        c = char
    elif (c[-1] <= char):
        c += char
    elif (c[-1] > char):
        if (len(r) < len(c)):
            r = c
            c = char
        else:
            c = char
if (len(c) > len(r)):
    r = c
print(r)

You can improve your algorithm by noticing that the string can be broken into runs of ordered substrings of maximal length. Any ordered substring must be contained in one of these runs

This allows you to just iterate once through the string O(n)

def longest_substring(string):
    curr, subs = '', ''
    for char in string:
        if not curr or char >= curr[-1]:
            curr += char
        else:
            curr, subs = '', max(curr, subs, key=len)
    return max(curr, subs, key=len)

s = 'cyqfjhcclkbxpbojgkar'
longest = ""
max =""

for i in range(len(s) -1):
    if(s[i] <= s[i+1] ):
       longest = longest + s[i]
       if(i==len(s) -2):
           longest = longest + s[i+1]
    else:
        longest  = longest + s[i]        
        if(len(longest) > len(max)):
            max = longest
        longest = ""        

if(len(s) == 1):
    longest = s


if(len(longest) > len(max)):
    print("Longest substring in alphabetical order is: " + longest)
else:
    print("Longest substring in alphabetical order is: " + max)

Try changing this:

        if len(set(substr)) != (end - start): # found duplicates or EOS
            break
        if (ord(max(sorted(substr))) - ord(min(sorted(substr))) + 1) == len(substr):

to this:

        if len(substr) != (end - start): # found duplicates or EOS
            break
        if sorted(substr) == list(substr):

That will display ccl for your example input string. The code is simpler because you're trying to solve a simpler problem :-)

Tags:

Python