Python最长字母序子串问题：《计算机科学导论与Python编程》作业咨询

Got it, let's work through this problem together. The goal is to find the longest substring in a given lowercase string where characters are in alphabetical order. And if there are multiple substrings with the same maximum length, we need to return the first one we encounter.

Approach #

Here's a straightforward, easy-to-follow way to tackle this:

• Start by initializing two variables: current_sub to track the substring we're currently building (starts with the first character of the string), and longest_sub to keep the longest valid substring we've found so far (also starts with the first character).
• Iterate through each character in the string starting from the second one:
  • If the current character is greater than or equal to the last character in current_sub, append it to current_sub (since it maintains the alphabetical order).
  • If not, compare the length of current_sub with longest_sub. If current_sub is longer, update longest_sub to be current_sub, then reset current_sub to the current character (starting a new potential substring).
• After the loop ends, we need one final check: the last current_sub might be the longest one, so we compare it again with longest_sub and update if needed.
• Finally, output the result.

Python Code Implementation #

# Replace this with your input string
s = 'azcbobobegghakl'

# Handle edge case where input string is empty
if not s:
    print("Longest substring in alphabetical order is: ")
else:
    current_sub = s[0]
    longest_sub = s[0]
    
    for char in s[1:]:
        # Check if current character continues the alphabetical order
        if char >= current_sub[-1]:
            current_sub += char
        else:
            # Update longest substring if current is longer
            if len(current_sub) > len(longest_sub):
                longest_sub = current_sub
            # Reset current substring to start with current character
            current_sub = char
    
    # Final check for the last substring in case it's the longest
    if len(current_sub) > len(longest_sub):
        longest_sub = current_sub
    
    print(f"Longest substring in alphabetical order is: {longest_sub}")

Explanation #

• Edge Case Handling: We first check if the input string is empty to avoid index errors and return an appropriate message.
• Tracking Substrings: current_sub grows as long as the next character maintains alphabetical order. When it can't, we check if this substring is the longest we've seen so far, then start fresh.
• Final Check: The loop ends before we can compare the last current_sub, so this step ensures we don't miss a substring that might be the longest one (like if the entire string is in alphabetical order).

Testing this code with your example input 'azcbobobegghakl' will output Longest substring in alphabetical order is: beggh, which matches the expected result. If you have a string like 'abcbcd', it will return abc (the first of two longest substrings), which aligns with the problem's requirement.

内容的提问来源于stack exchange，提问作者Pete Smyth