Finding Longest Substring In Alphabetical Order

EDIT: I am aware that a question with similar task was already asked in SO but I'm interested to find out the problem in this specific piece of code. I am also aware that this prob

Solution 1:

There are many things to improve in your code but making minimum changes so as to make it work. The problem is you should have if last_pos(i) != None: in your for loop (i instead of i+1) and you should compare diff (not diff - 1) against maxLen. Please read other answers to learn how to do it better.

for i in range(len(s)):
    iflast_pos(i) != None:
        diff = last_pos(i) - i + 1if diff > maxLen:
        maxLen = diffstartPos=iendPos= startPos + diff - 1

Solution 2:

Here. This does what you want. One pass, no need for recursion.

def find_longest_substring_in_alphabetical_order(s):
    groups= []
    cur_longest =''
    prev_char =''for c in s.lower():
        if prev_char and c < prev_char:
            groups.append(cur_longest)
            cur_longest = c
        else:
            cur_longest += c
        prev_char = c
    returnmax(groups, key=len) if groupselse s

Using it:

>>> find_longest_substring_in_alphabetical_order('hixwluvyhzzzdgd')
'luvy'>>> find_longest_substring_in_alphabetical_order('eseoojlsuai')
'jlsu'>>> find_longest_substring_in_alphabetical_order('drurotsxjehlwfwgygygxz')
'ehlw'

Note: It will probably break on strange characters, has only been tested with the inputs you suggested. Since this is a "homework" question, I will leave you with the solution as is, though there is still some optimization to be done, I wanted to leave it a little bit understandable.

Solution 3:

You can use nested for loops, slicing and sorted. If the string is not all lower-case then you can convert the sub-strings to lower-case before comparing using str.lower:

defsolve(strs):
  maxx = ''for i in xrange(len(strs)):
      for j in xrange(i+1, len(strs)):
          s = strs[i:j+1]
          if''.join(sorted(s)) == s:
              maxx = max(maxx, s, key=len)
          else:
              breakreturn maxx

Output:

>>> solve('hixwluvyhzzzdgd')
'luvy'>>> solve('eseoojlsuai')
'jlsu'>>> solve('drurotsxjehlwfwgygygxz')
'ehlw'

Solution 4:

Python has a powerful builtin package itertools and a wonderful function within groupby

An intuitive use of the Key function can give immense mileage.

In this particular case, you just have to keep a track of order change and group the sequence accordingly. The only exception is the boundary case which you have to handle separately

Code

deffind_long_cons_sub(s):
    classKey(object):
        '''
        The Key function returns 
            1: For Increasing Sequence
            0: For Decreasing Sequence
        '''def__init__(self):
            self.last_char = Nonedef__call__(self, char):
            resp = Trueif self.last_char:
                resp = self.last_char < char
            self.last_char = char
            return resp
    deffind_substring(groups):
        '''
        The Boundary Case is when an increasing sequence
        starts just after the Decresing Sequence. This causes
        the first character to be in the previous group.
        If you do not want to handle the Boundary Case
        seperately, you have to mak the Key function a bit 
        complicated to flag the start of increasing sequence'''yieldnext(groups)
        try:
            whileTrue:
                yieldnext(groups)[-1:] + next(groups)
        except StopIteration:
            pass
    groups = (list(g) for k, g in groupby(s, key = Key()) if k)
    #Just determine the maximum sequence based on lengthreturn''.join(max(find_substring(groups), key = len))

Result

>>> find_long_cons_sub('drurotsxjehlwfwgygygxz')
'ehlw'>>> find_long_cons_sub('eseoojlsuai')
'jlsu'>>> find_long_cons_sub('hixwluvyhzzzdgd')
'luvy'

Solution 5:

Simple and easy.

Code :

s = 'hixwluvyhzzzdgd' 
r,p,t = '','',''for c in s:
    if p <= c:
        t += c
        p = c
    else:
        iflen(t) > len(r):
            r = t
        t,p = c,c
iflen(t) > len(r):
    r = t
print'Longest substring in alphabetical order is: ' + r

Output :

Longest substring in alphabetical order which appeared first: luvy