Longest substring in a string

Python Help
1

Hello,

I have the following assignment:

’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ‘’ ’ ’ ‘’ ’ ’ ’

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 no idea on the outline of this algoroithm. Could somoeone please give me an idea?

Thank you.

2

Can you find a substring in alphabetical order?

substring = ''
prev_char = ''
for c in string:
    if string >= prev_char:
        # Still in alphabetical order!
        # Keep accumulating characters in the substring
        ...
    else:
        print("Just seen a substring", substring, len(substring))
        # Not in alphabetical order, so start a new substring
        substring = ''
    prev_char = c

Once you have done that, it should be easy to modify it to track the longest substring.

Warning: I have not tried this myself.

3

The first question is: Do you understand the problem enough to do it by hand? Can you write out on a piece of note paper a process where you build up the answer bit-by-bit?

For example, one approach might be to go through the string character-by-character, keeping track of the current ordered substring as well as the longest ordered substring you’ve seen before:

current character current substring longest substring
a a a
z az az
c c az
… … …

You might find another approach that is more intuitive to you. But you need to find an approach that you can do and get the right answer. And they do give you two examples to check your work.

One of the first things you can do is write yourself a test:

#!python

def longest_sorted_substring(s):
    # TODO
    return s

def test_longest_sorted_substring():
    assert longest_sorted_substring('azcbobobegghakl') == 'beggh'
    assert longest_sorted_substring('abcbcd') == 'abc'

if __name__ == '__main__':
    test_longest_sorted_substring()

This will help you check things as you work through the problem.

I find it often helps to think of the simplest cases first:

  • ''
  • 'a'
  • 'b'
  • 'ab' and 'ba'
  • 'abc', 'acb', 'bac', 'bca', 'cab', 'cba'

What should each result be? You can add them to your tests, as well as use them to work through some ideas for algorithms.