How to take out the longest substring by alphabetical order in a list?

user_14238316 0
Viewed 86

For example, the initial list L=["by","article","circle","for","line","dance","effort"], and I want to take out the["article","circle","for","line"] as the result. Because the first alpha in L is (b,a,c,f,l,d,e) and the consequence of (a,c,f,l)is the longer than (d,e), so the result is ["article","circle","for","line"]. How to fix my code? I'm new so I'm so confusing with sorted() and nested loop.

def find_longest_consisting(test_case):
    if not test_case:
        return []
    result = []
    for i in range(len(test_case)):
        for j in range(i + len(result) + 1):
            substring = test_case[i:j]
            if len(substring) != (j - i):
                break
            if sorted(substring) == list(substring):
                result = substring
    return result

test_cases = ["by","article","circle","for","line","dance","effort"]
test_result = find_longest_consisting(test_cases)
print(test_result)
substring list sorting python
2 Answers

The fastest way to do this is by maintaining a "longest" list and comparing it's length to the current sublist when a change in ordering is encountered, assigning the current sublist to the longest if it is longer. This only requires one iteration over the list to get the result.

def longest_group(lst):
    longest = []
    current = lst[:1]
    for i in range(1, len(lst)):
        if lst[i][0] <= lst[i-1][0]:
            if len(current) > len(longest):
                longest = current
            current = [lst[i]]
        else:
            current.append(lst[i])
    if len(current) > len(longest):
        longest = current
    return longest

print(longest_group(["by","article","circle","for","line","dance","effort"]))
print(longest_group(["zoo","slack","egg"]))

Output:

['article', 'circle', 'for', 'line']
['zoo']

For your ["by","article","circle","for","line","dance","effort"] list this is 10x faster than sorting all the combinations from the list. See https://rextester.com/JEJOAE73859 for a demo.

user_94737640

A simple alternative to doing your own nested loop to check different subsets is to use itertools.combinations:

from itertools import combinations
def longest_group(lst):
    return max((
        lst[a:b]
        for a, b in combinations(range(len(lst)+1), 2)
        if sorted(lst[a:b]) == lst[a:b]
    ), key=len) if lst else lst

If speed is more important than simplicity, the blazing-fast version would be to iterate over the list and track the range that corresponds to the longest sorted slice:

def longest_group(lst):
    a, b, i = 0, 0, 0
    for j, e in enumerate(lst[1:]):
        if e < lst[j]:
            if j - i > b - a:
                a, b = i, j
            i = j + 1
    if len(lst) - i > b - a + 1:
        a, b = i, len(lst)
    return lst[a:b+1]
user_37997590
Related