Find the longest substring in alphabetical order

Question

I have this code, which I found in another thread, but it sorts the substring with adjacent characters, not in alphabetical order. How to fix it in alphabetical order? It prints lk and I want to print ccl . Thanks

ps: I'm a beginner in python

 s = 'cyqfjhcclkbxpbojgkar' from itertools import count def long_alphabet(input_string): maxsubstr = input_string[0:0] # empty slice (to accept subclasses of str) for start in range(len(input_string)): # O(n) for end in count(start + len(maxsubstr) + 1): # O(m) substr = input_string[start:end] # O(m) if len(set(substr)) != (end - start): # found duplicates or EOS break if (ord(max(sorted(substr))) - ord(min(sorted(substr))) + 1) == len(substr): maxsubstr = substr return maxsubstr bla = (long_alphabet(s)) print "Longest substring in alphabetical order is: %s" %bla 

Answer 1

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): 

:

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

ccl will be displayed for the input line of your example. The code is simpler because you are trying to solve a simpler problem :-)

Answer 2

 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) 

Answer 3

You can improve your algorithm by noting that a string can be broken down into runs of ordered substrings of maximum length. Any ordered substring must be contained in one of these runs.

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

 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) 

Answer 4

In a recursive way, you can import count from itertools

Or define the same method:

 def loops( I=0, S=1 ): n = I while True: yield n n += S 

With this method, you can get the endpoint value when you create a substring in your allitic process.

Now the anallize method looks (based on spacegame and Mr. Tim Petter's suggestion )

 def anallize(inStr): # empty slice (maxStr) to implement # str native methods # in the anallize search execution maxStr = inStr[0:0] # loop to read the input string (inStr) for i in range(len(inStr)): # loop to sort and compare each new substring # the loop uses the loops method of past # I = sum of: # (i) current read index # (len(maxStr)) current answer length # and 1 for o in loops(i + len(maxStr) + 1): # create a new substring (newStr) # the substring is taked: # from: index of read loop (i) # to: index of sort and compare loop (o) newStr = inStr[i:o] if len(newStr) != (o - i):# detect and found duplicates break if sorted(newStr) == list(newStr):# compares if sorted string is equal to listed string # if success, the substring of sort and compare is assigned as answer maxStr = newStr # return the string recovered as longest substring return maxStr 

Finally, for verification or execution it pours out:

 # for execution pourposes of the exercise: s = "azcbobobegghakl" print "Longest substring in alphabetical order is: " + anallize( s ) 

A great piece of this work has begun: spacegame and was attended by Mr. Tim Petters , used in native str methods and code reuse.

Answer:

The longest substring in alphabetical order: ccl

Answer 5

Compared to Python, comparison is easy compared to a java script where ASCII values ​​should be compared. According to python

a> b gives Boolean False, and b> a gives Boolean truth

Using this, the longest substring in alphabetical order can be found using the following algorithm:

 def comp(a,b): if a<=b: return True else: return False s = raw_input("Enter the required sting: ") final = [] nIndex = 0 temp = [] for i in range(nIndex, len(s)-1): res = comp(s[i], s[i+1]) if res == True: if temp == []: #print i temp.append(s[i]) temp.append(s[i+1]) else: temp.append(s[i+1]) final.append(temp) else: if temp == []: #print i temp.append(s[i]) final.append(temp) temp = [] lengths = [] for el in final: lengths.append(len(el)) print lengths print final lngStr = ''.join(final[lengths.index(max(lengths))]) print "Longest substring in alphabetical order is: " + lngStr 

Answer 6

Use the list and max function to significantly reduce code.

 actual_string = 'azcbobobegghakl' strlist = [] i = 0 while i < len(actual_string)-1: substr = '' while actial_string[i + 1] > actual_string[i] : substr += actual_string[i] i += 1 if i > len(actual_string)-2: break substr += actual-string[i] i += 1 strlist.append(subst) print(max(strlist, key=len)) 

Answer 7

 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) 

Answer 8

A slightly different implementation, creating a list of all substrings in alphabetical order and returning the longest:

 def longest_substring(s): in_orders = ['' for i in range(len(s))] index = 0 for i in range(len(s)): if (i == len(s) - 1 and s[i] >= s[i - 1]) or s[i] <= s[i + 1]: in_orders[index] += s[i] else: in_orders[index] += s[i] index += 1 return max(in_orders, key=len) 

Answer 9

 s = "azcbobobegghakl" ls = "" for i in range(0, len(s)-1): b = "" ss = "" j = 2 while j < len(s): ss = s[i:i+j] b = sorted(ss) str1 = ''.join(b) j += 1 if str1 == ss: ks = ss else: break if len(ks) > len(ls): ls = ks print("The Longest substring in alphabetical order is "+ls) 

Answer 10

It worked for me

 s = 'cyqfjhcclkbxpbojgkar' lstring = s[0] slen = 1 for i in range(len(s)): for j in range(i,len(s)-1): if s[j+1] >= s[j]: if (j+1)-i+1 > slen: lstring = s[i:(j+1)+1] slen = (j+1)-i+1 else: break print("Longest substring in alphabetical order is: " + lstring) 

Conclusion: The longest substring in alphabetical order: ccl

Answer 11

 input_str = "cyqfjhcclkbxpbojgkar" length = len(input_str) # length of the input string iter = 0 result_str = '' # contains latest processed sub string longest = '' # contains longest sub string alphabetic order while length > 1: # loop till all char processed from string count = 1 key = input_str[iter] #set last checked char as key result_str += key # start of the new sub string for i in range(iter+1, len(input_str)): # discard processed char to set new range length -= 1 if(key <= input_str[i]): # check the char is in alphabetic order key = input_str[i] result_str += key # concatenate the char to result_str count += 1 else: if(len(longest) < len(result_str)): # check result and longest str length longest = result_str # if yes set longest to result result_str = '' # re initiate result_str for new sub string iter += count # update iter value to point the index of last processed char break if length is 1: # check for the last iteration of while loop if(len(longest) < len(result_str)): longest = result_str print(longest); 

Answer 12

Wow, some really impressive code snippets here ... I want to add my solution, since I think it is pretty clean:

 s = 'cyqfjhcclkbxpbojgkar' res = '' tmp = '' for i in range(len(s)): tmp += s[i] if len(tmp) > len(res): res = tmp if i > len(s)-2: break if s[i] > s[i+1]: tmp = '' print("Longest substring in alphabetical order is: {}".format(res)) 

Answer 13

Without using the library, but using the ord() function, which returns the ascii value for the character. Assumption: the input will be lowercase and no special characters are used

 s = 'azcbobobegghakl' longest = '' for i in range(len(s)): temp_longest=s[i] for j in range(i+1,len(s)): if ord(s[i])<=ord(s[j]): temp_longest+=s[j] i+=1 else: break if len(temp_longest)>len(longest): longest = temp_longest print(longest) 

Answer 14

find the longest substring in alphabetical order in Python

in python shell 'a' < 'b' or 'a' <= 'a' is True

 result = '' temp = '' for char in s: if (not temp or temp[-1] <= char): temp += char elif (temp[-1] > char): if (len(result) < len(temp)): result = temp temp = char if (len(temp) > len(result)): result = temp print('Longest substring in alphabetical order is:', result) 

Answer 15

 s=input() temp=s[0] output=s[0] for i in range(len(s)-1): if s[i]<=s[i+1]: temp=temp+s[i+1] if len(temp)>len(output): output=temp else: temp=s[i+1] print('Longest substring in alphabetic order is:' + output) 

Answer 16

Another way:

 s = input("Please enter a sentence: ") count = 0 maxcount = 0 result = 0 for char in range(len(s)-1): if(s[char]<=s[char+1]): count += 1 if(count > maxcount): maxcount = count result = char + 1 else: count = 0 startposition = result - maxcount print("Longest substring in alphabetical order is: ", s[startposition:result+1])