I need help on a problem that I am doing in a course. The exact details are below:

Assume s is a string of lower case characters.

Write a program that prints the longest substring of s in which the letters occur in alphabetical order.

For example, if s = 'azcbobobegghakl', then your program should print

"Longest substring in alphabetical order is: beggh"

In the case of ties, print the first substring. For example, if s = 'abcbcd', then your program should print

"Longest substring in alphabetical order is: abc"

I have written some code that achieves some correct answers but not all and I am unsure why.

This is my code




s = 'vettmlxvn'

alphabet = "abcdefghijklmnopqrstuvwxyz"
substring = ""
highest_len = 0
highest_string = ""
counter = 0


for letter in s:
    counter  = 1
    if s.index(letter) == 0:
        substring = substring   letter
        highest_len = len(substring)
        highest_string = substring
    else:
        x = alphabet.index(substring[-1])
        y = alphabet.index(letter)
        if y >= x:
            substring = substring   letter
            if counter == len(s) and len(substring) > highest_len:
                highest_len = len(substring)
                highest_string = substring
        else:
            if len(substring) > highest_len:
                highest_len = len(substring)
                highest_string = substring
                substring = ""   letter
            else:
                substring = ""   letter

print("Longest substring in alphabetical order is: "   highest_string)

When I test for this specific string it gives me "lxv" instead of the correct answer: "ett". I do not know why this is and have even tried drawing a trace table so I can trace variables and I should be getting "ett". Maybe I have missed something simple but can someone explain why it is not working.

I know there are probably easier ways to do this problem but I am a beginner in python and have been working on this problem for a long time.

Just want to know what is wrong with my code.

Thanks.

CodePudding user response：

Alternate Approach

Break input string into substrings
Where each substring is increasing
Find the longest substring

Code

def longest_increasing_substring(s):
    # Break s into substrings which are increasing
    incr_subs = []
    for c in s:
        if not incr_subs or incr_subs[-1][-1] > c:# check alphabetical order of last letter of current
                                                  # string to current letter
            incr_subs.append('')                  # Start new last substring since not in order
        incr_subs[-1]  = c                        # append to last substsring

    return max(incr_subs, key = len)              # substring with max length

Test

for s in ['vettmlxvn', 'azcbobobegghakl', 'abcbcd']:
    print(f'{s} -> {longest_increasing_substring(s)}')

Output

vettmlxvn -> ett
azcbobobegghakl -> beggh
abcbcd -> abc

CodePudding user response：

I solved your Problem with an alternate simpler approach.

You can compare 2 characters like numbers. a comes before b in the alphabet, that means the expression 'a' < 'b' is True

def longest_substring(s):
    # Initialize the longest substring
    longest = ""
    # Initialize the current substring
    current = ""
    # Loop through the string
    for i in range(len(s)):
        if i == 0:
            # If it's the first letter, add it to the current substring
            current  = s[i]
        else:
            if s[i] >= s[i-1]:
                # If the current letter is greater than or equal to the previous letter,
                # add it to the current substring
                current  = s[i]
            else:
                # If the current letter is less than the previous letter,
                # check if the current substring is longer than the longest substring
                # and update the longest substring if it is
                if len(current) > len(longest):
                    longest = current
                current = s[i]
    # Once the loop is done,
    # check again if the current substring is longer than the longest substring
    if len(current) > len(longest):
        longest = current
    return longest

print(longest_substring("azcbobobegghakl"))
print(longest_substring("abcbcd"))
print(longest_substring("abcdefghijklmnopqrstuvwxyz"))
print(longest_substring("vettmlxvn"))

Output:

beggh
abc
abcdefghijklmnopqrstuvwxyz
ett

I haven't figured out what's wrong with your code yet. I will update this if I figured it out.

Edit

So commented some stuff out and changed one thing.

Here's the working code:

s = 'vettmlxvn'

alphabet = "abcdefghijklmnopqrstuvwxyz"
substring = ""
highest_len = 0
highest_string = ""
counter = 0

for letter in s:
    counter  = 1
    if s.index(letter) == 0:
        substring = substring   letter
        # highest_len = len(substring)
        # highest_string = substring
    else:
        x = alphabet.index(substring[-1])
        y = alphabet.index(letter)
        if y >= x:
            substring = substring   letter
            if counter == len(s) and len(substring) > highest_len:
                highest_len = len(substring)
                highest_string = substring
        else:
            if len(substring) > len(highest_string): # changed highest_len to len(highest_string)
                #highest_len = len(substring)
                highest_string = substring
                substring = ""   letter
            else:
                substring = ""   letter

print("Longest substring in alphabetical order is: "   highest_string)

You are overwriting highest_string at the wrong time. Only overwrite it if the substrings ends and after checking if it's greater than the longest found before.

Outputs:

Longest substring in alphabetical order is: ett