알파벳 순서로 가장 긴 하위 문자열

Question

알파벳 순서로 문자가 나오는 s 중에서 가장 긴 하위 문자열을 인쇄하는 프로그램을 작성하십시오. 예를 들어, S의 = 'azcbobobegghakl'있다면, 당신의 프로그램은 알파벳 순서로

가장 긴 문자열이 인쇄해야합니다 : 관계의 경우

가 첫 번째 문자열을 인쇄 beggh. 예를 들어, S의 = 'abcbcd'있다면, 당신의 프로그램은 인쇄해야

알파벳 순서로

가장 긴 부분 문자열은 다음과 같습니다 ABC 여기

Answer 1

당신은 갈 내가 코드를 완료하는 데 도움이 된 것 EDX 학생 :

from itertools import count 

def long_sub(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(substr) != (end - start): # found duplicates or EOS 
       break 
      if sorted(substr) == list(substr): 
       maxsubstr = substr 
    return maxsubstr 

sub = (long_sub(s)) 
print "Longest substring in alphabetical order is: %s" %sub 

을

Answer 2

다음 코드는 reduce 방법을 사용하여 문제 해결 :

solution = '' 

def check(substr, char): 
    global solution 
    last_char = substr[-1] 
    substr = (substr + char) if char >= last_char else char 
    if len(substr) > len(solution): 
     solution = substr 
    return substr 

def get_largest(s): 
    global solution 
    solution = '' 
    reduce(check, list(s)) 
    return solution 

Answer 3

을이 모든 당신이 문자열 (들)이 가장 긴 서브를 찾을 필요로하는 가정합니다 알파벳 순서로 문자열.

옵션 itertools 수입 C에서

test = s[0]  # seed with first letter in string s 
best = ''  # empty var for keeping track of longest sequence 

for n in range(1, len(s)): # have s[0] so compare to s[1] 
    if len(test) > len(best): 
     best = test 
    if s[n] >= s[n-1]: 
     test = test + s[n] # add s[1] to s[0] if greater or equal 
    else:      # if not, do one of these options 
     test = s[n] 

print "Longest substring in alphabetical order is:", best 

옵션 B

maxSub, currentSub, previousChar = '', '', '' 
for char in s: 
    if char >= previousChar: 
     currentSub = currentSub + char 
     if len(currentSub) > len(maxSub): 
      maxSub = currentSub 
    else: currentSub = char 
    previousChar = char 
print maxSub 

옵션 C

matches = [] 
current = [s[0]] 
for index, character in enumerate(s[1:]): 
    if character >= s[index]: current.append(character) 
    else: 
     matches.append(current) 
     current = [character] 
print "".join(max(matches, key=len)) 

옵션 D

def longest_ascending(s): 
    matches = [] 
    current = [s[0]] 
    for index, character in enumerate(s[1:]): 
     if character >= s[index]: 
      current.append(character) 
     else: 
      matches.append(current) 
      current = [character] 
    matches.append(current) 
    return "".join(max(matches, key=len)) 
print(longest_ascending(s))