Найти самую длинную подстроку в алфавитном порядке

Question

У меня есть этот код, который я нашел в другой теме, но он сортирует подстроку смежными символами, а не в алфавитном порядке. Как исправить его в алфавитном порядке? Он печатает lk, и я хочу напечатать ccl. Благодаря

пс: Я новичок в 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

Попробуйте изменить это:

 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 для примера ввода строка. Код проще, потому что вы пытаетесь решить более простую задачу :-)

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

Вы можете улучшить свой алгоритм, заметив, что строка может быть разбита на пробегов упорядоченных подстроки максимальной длины. Любая упорядоченная подстрока должна содержаться в одной из этих серий

Это позволяет вам просто итерация один раз через струнные О (п)

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

В сравнении Python символьного легко по сравнению с Java-скриптом, где значение ASCII должны быть сопоставлены. По питону

а> Ь дает логическое значение False и Ь> а дает логический относящейся к истинному норду

Используя этим самую длинную подстроку в алфавитном порядке можно найти, используя следующий алгоритм:

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 5

Немного отличается реализация, создание списка всех подстрок в алфавитном порядке и возвращает самый длинный один:

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 6

В рекурсивным образом, вы можете я Mport количество от itertools

Или определить тот же метод:

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

С помощью этого метода можно получить значение конечной точки, когда вы создаете любую подстроку в вашем anallitic процессе.

Теперь выглядит метод anallize (на основе spacegame выпуска и г-н Tim Petters предложение)

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 

Наконец, для тестирования или выполнения pourposes:

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

Большая часть эта работа началась с: spacegame и присутствовал наTim Petters, используется для использования методов str str и повторного использования кода.

Ответ:

Серия подстроки в алфавитном порядке является: CCl

Answer 7

Другой способ:

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

Answer 8

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 9

Используйте список и максимальная функция для уменьшения кода резко.

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 10

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)