count - 按字母顺序排列的最长子串

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

这些都假设您有一个字符串，并且需要按字母顺序查找最长的子字符串。

选项 A

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

Answer 3

The following code solves the problem using the reduce method:

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