Search for the longest substring in alphabetical order

Question

EDIT . I know that a question with a similar problem has already been asked in SO, but I am interested to find out the problem in this particular piece of code. I also know that this problem can be solved without using recursion.

The challenge is to write a program that finds (and prints) the longest substring in which letters appear in alphabetical order. If more than 1 equally long sequences were found, then you need to print the first. For example, the output for the string abczabcd would be abcz .

I solved this problem with recursion, which seemed to pass my manual tests. However, when I run a set of automatic tests that generate random strings, I noticed that in some cases the output is incorrect. For example:

if s = 'hixwluvyhzzzdgd' , output hix instead of luvy

if s = 'eseoojlsuai' , exit eoo instead of jlsu

if s = 'drurotsxjehlwfwgygygxz' , exit dru instead of ehlw

After some time, I could not understand what is especially important in these lines, which cause an error.

This is my code:

 pos = 0 maxLen = 0 startPos = 0 endPos = 0 def last_pos(pos): if pos < (len(s) - 1): if s[pos + 1] >= s[pos]: pos += 1 if pos == len(s)-1: return len(s) else: return last_pos(pos) return pos for i in range(len(s)): if last_pos(i+1) != None: diff = last_pos(i) - i if diff - 1 > maxLen: maxLen = diff startPos = i endPos = startPos + diff print s[startPos:endPos+1] 

Answer 1

There are many things that need to be improved in the code, but with minimal changes to make it work. The problem is that the for loop ( i instead of i+1 ) should have if last_pos(i) != None: , and you should compare diff (not diff - 1 ) with maxLen . Please read the other answers to find out how to do this better.

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

Answer 2

Here. It does what you want. One pass, no recursion needed.

 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 return max(groups, key=len) if groups else 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, it was tested only with the inputs you enclosed. Since this is a "homework" question, I will leave you with the solution as it is, although there is still some kind of optimization, I would like to leave it a little understandable.

Answer 3

You can use nested for loops, sliced, and sorted . If the string is not all lowercase, you can convert the substrings to lowercase before comparing with str.lower :

 def solve(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: break return maxx 

Output:

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

Answer 4

Here is a one-pass solution with a fast cycle. He reads each character only once. Inside cycles, operations are limited

• 1 string comparison (1 char x 1 char)
• 1 integer increment
• 2 integer subtractions
• 1 integer comparison
• 1 to 3 whole assignments
• 1 line assignment

Containers are not used. Function calls are not made. An empty string is processed without special code. All character codes, including chr (0), are handled appropriately. If there is a relationship for the longest alphabetical substring, the function returns the first winning substring that it encountered. Case is ignored for alphabetical purposes, but case is stored in the output substring.

 def longest_alphabetical_substring(string): start, end = 0, 0 # range of current alphabetical string START, END = 0, 0 # range of longest alphabetical string yet found prev = chr(0) # previous character for char in string.lower(): # scan string ignoring case if char < prev: # is character out of alphabetical order? start = end # if so, start a new substring end += 1 # either way, increment substring length if end - start > END - START: # found new longest? START, END = start, end # if so, update longest prev = char # remember previous character return string[START : END] # return longest alphabetical substring 

Result

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

Answer 5

Python has a powerful built-in itertools package and a great feature in groupby

Intuitive use of the Key function can give you huge mileage

In this particular case, you just need to track the change in order and group the sequence accordingly. The one exception is the boundary case, which you must handle separately

the code

 def find_long_cons_sub(s): class Key(object): ''' The Key function returns 1: For Increasing Sequence 0: For Decreasing Sequence ''' def __init__(self): self.last_char = None def __call__(self, char): resp = True if self.last_char: resp = self.last_char < char self.last_char = char return resp def find_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''' yield next(groups) try: while True: yield next(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 length return ''.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' 

Answer 6

a lot more cycles, but he does the job

 s = raw_input("Enter string") fin="" s_pos =0 while s_pos < len(s): n=1 lng=" " for c in s[s_pos:]: if c >= lng[n-1]: lng+=c n+=1 else : break if len(lng) > len(fin): fin= lng`enter code here` s_pos+=1 print "Longest string: " + fin 

Answer 7

 def find_longest_order(): `enter code here`arr = [] `enter code here`now_long = '' prev_char = '' for char in s.lower(): if prev_char and char < prev_char: arr.append(now_long) now_long = char else: now_long += char prev_char = char if len(now_long) == len(s): return now_long else: return max(arr, key=len) def main(): print 'Longest substring in alphabetical order is: ' + find_longest_order() main() 

Answer 8

Simple and easy.

The code:

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

Exit:

 Longest substring in alphabetical order which appeared first: luvy 

Answer 9

Simple and straightforward:

 s = "abcbcd" #The original string l = len(s) #The length of the original string maxlenstr = s[0] #maximum length sub-string, taking the first letter of original string as value. curlenstr = s[0] #current length sub-string, taking the first letter of original string as value. for i in range(1,l): #in range, the l is not counted. if s[i] >= s[i-1]: #If current letter is greater or equal to previous letter, curlenstr += s[i] #add the current letter to current length sub-string else: curlenstr = s[i] #otherwise, take the current letter as current length sub-string if len(curlenstr) > len(maxlenstr): #if current cub-string length is greater than max one, maxlenstr = curlenstr; #take current one as max one. print("Longest substring in alphabetical order is:", maxlenstr) 

Answer 10

 s = input("insert some string: ") start = 0 end = 0 temp = "" while end+1 <len(s): while end+1 <len(s) and s[end+1] >= s[end]: end += 1 if len(s[start:end+1]) > len(temp): temp = s[start:end+1] end +=1 start = end print("longest ordered part is: "+temp) 

Answer 11

I believe this question has been asked for CS6.00.1x on EDX. Here is what I came up with.

 s = raw_input("Enter the string: ") longest_sub = "" last_longest = "" for i in range(len(s)): if len(last_longest) > 0: if last_longest[-1] <= s[i]: last_longest += s[i] else: last_longest = s[i] else: last_longest = s[i] if len(last_longest) > len(longest_sub): longest_sub = last_longest print(longest_sub) 

Answer 12

I came up with this solution

 def longest_sorted_string(s): max_string = '' for i in range(len(s)): for j in range(i+1, len(s)+1): string = s[i:j] arr = list(string) if sorted(string) == arr and len(max_string) < len(string): max_string = string return max_string 

Answer 13

Assuming this is an Edx course: before this question, we did not talk about strings and their extended operations in python. So, I just go through the looping and conditional statements

 string ="" #taking a plain string to represent the then generated string present ="" #the present/current longest string for i in range(len(s)): #not len(s)-1 because that totally skips last value j = i+1 if j>= len(s): j=i #using s[i+1] simply throws an error of not having index if s[i] <= s[j]: #comparing the now and next value string += s[i] #concatinating string if above condition is satisied elif len(string) != 0 and s[i] > s[j]: #don't want to lose the last value string += s[i] #now since s[i] > s[j] #last one will be printed if len(string) > len(present): #1 > 0 so from there we get to store many values present = string #swapping to largest string string = "" if len(string) > len(present): #to swap from if statement present = string if present == s[len(s)-1]: #if no alphabet is in order then first one is to be the output present = s[0] print('Longest substring in alphabetical order is:' + present) 

Answer 14

I agree with @Abhijit about the power of itertools.groupby() , but I used a simpler approach to (ab) using it, and avoided problems with the boundary case:

 from itertools import groupby LENGTH, LETTERS = 0, 1 def longest_sorted(string): longest_length, longest_letters = 0, [] key, previous_letter = 0, chr(0) def keyfunc(letter): nonlocal key, previous_letter if letter < previous_letter: key += 1 previous_letter = letter return key for _, group in groupby(string, keyfunc): letters = list(group) length = len(letters) if length > longest_length: longest_length, longest_letters = length, letters return ''.join(longest_letters) print(longest_sorted('hixwluvyhzzzdgd')) print(longest_sorted('eseoojlsuai')) print(longest_sorted('drurotsxjehlwfwgygygxz')) print(longest_sorted('abcdefghijklmnopqrstuvwxyz')) 

OUTPUT

 > python3 test.py luvy jlsu ehlw abcdefghijklmnopqrstuvwxyz > 

Answer 15

 s = 'azcbobobegghakl' i=1 subs=s[0] subs2=s[0] while(i<len(s)): j=i while(j<len(s)): if(s[j]>=s[j-1]): subs+=s[j] j+=1 else: subs=subs.replace(subs[:len(subs)],s[i]) break if(len(subs)>len(subs2)): subs2=subs2.replace(subs2[:len(subs2)], subs[:len(subs)]) subs=subs.replace(subs[:len(subs)],s[i]) i+=1 print("Longest substring in alphabetical order is:",subs2) 

Answer 16

 s = 'gkuencgybsbezzilbfg' x = s.lower() y = '' z = [] #creating an empty listing which will get filled for i in range(0,len(x)): if i == len(x)-1: y = y + str(x[i]) z.append(y) break a = x[i] <= x[i+1] if a == True: y = y + str(x[i]) else: y = y + str(x[i]) z.append(y) # fill the list y = '' # search of 1st longest string L = len(max(z,key=len)) # key=len takes length in consideration for i in range(0,len(z)): a = len(z[i]) if a == L: print 'Longest substring in alphabetical order is:' + str(z[i]) break 

Answer 17

 first_seq=s[0] break_seq=s[0] current = s[0] for i in range(0,len(s)-1): if s[i]<=s[i+1]: first_seq = first_seq + s[i+1] if len(first_seq) > len(current): current = first_seq else: first_seq = s[i+1] break_seq = first_seq print("Longest substring in alphabetical order is: ", current)