0

So I was assigned a tasks of counting the longest substring in a string in which the letters occur in alphabetical order. I came up with an answer that works and is correct but to be frank, I'm having trouble understanding my own code.. please bear with me. I worked around my misunderstanding to produce working code. Why, in this example, would the variable longest == 4 instead of 5?

s = 'azcbobobegghakl'

count = 0
longest = 0
end = 0

for a in range(len(s) - 1):
    if s[a] <= s[a + 1]:      # is s[a] greater than or = to the next char in string?
        count += 1            # if it is, +1 to count
        if count > longest:   # if count is greater than longest (longest is current longest - 1), continue, otherwise keep counting
            longest = count   # new longest is the current count because it is longest
            end = a + 1       # since end is in this if block, it counts the iteration where count was last greater than the longest
    else:                     # when count is never greater than longest again the longest will be the length of the longest string
        count = 0

start = end - longest

"""
end is the last position in the longest string (here it is 11 or h) 
longest is length of the string (here it is 4)
so the end - longest characters = the start of string which is 7 or b
"""

print('Longest substring in alphabetical order is: ' + s[start:end + 1])
#prints the letters in s from position 7 to 11 + 1 (+1 because end = index 11 but it goes up to and not including 11)
Improve this question
2

3 Answers 3

Reset to default
3

When the below condition is true, this means you have at least a sub-string with length 2, but since you are starting the count from 0, you have longest one less than what you expect. 

s[a] <= s[a + 1]

So the solution is to initialize count to 1, which makes sense since a single letter will always be the longest sub-string in the initial case (unless you have an empty string, which you should handle).

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

That didn't work but I figured out why it didn't if you were curious, see my answer and tell me what you think.
You still need to change this line as such: start = end - longest + 1. If you change count=0 to count=1 in the two initializations, longest will now be giving you the true length of the longest sub-string. Since end is the last index of the longest sub-string, subtracting the sub-string goes to the last index before the sub-string starts, so you should add 1 to calculate the starting index of the sub-string.
That would make the output “eggh” where it should be “beggh”
Check this out: goo.gl/cExhru (sorry for the shortened link, but it is otherwise too long to fit in a comment). I ran it using the tool Yaroslav mentioned in his comment and it seems to be producing the correct output.
oh I see what you meant! I forgot to initialize the ‘else’ count to 1 as well, that makes much more sense. Thank you for clarifying. This solution will definitely work.
0

This code is counting the gaps. That is to say that you are looking for when the difference between two letters meets a criteria. This is a diff, and you are counting the successful diffs, which will be one less than the length needed to get that number of diffs.

You will likely need: 

start = end - longest - 1

Or adjust count or end.

Improve this answer

Comments

0

I figured it out, I suppose that one it runs the 11th iteration (h < a) it realizes that h is not less than a, so it sets the count back to 0 rather than counting h as the 5th letter. Essentially longest will always be one short of the actual length of the longest alphabetical substring due to the final evaluation in the longest substring being equal to false which sets it back to 0 rather than 5. Since longest == 4 that's the longest can actually be defined as the number of true evaluations in a row.

So I should probably rename the variable longest because it is slightly misleading here because it is not actually the longest, but how many characters after the before the final character in the longest substring.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.