FInding longest substring in abc order

Question

So the question is to find the longest substring in abc order given a string, s, so this piece of code works in some cases but so this s that I defined it does work and I have no clue as to why

s = 'vwjxxumjb'
longest = s[0]
current = s[0]

for c in s[1:]:
    if c >= current[-1]:
        current += c
    if len(current) > len(longest):
        longest = current
    else:
        current = c

print ("Longest substring in alphabetical order is:", longest)

See this question: [Longest increasing subsequence](https://stackoverflow.com/questions/3992697/longest-increasing-subsequence) — Peter Wood, Jun 12 '18 at 23:04
@PeterWood That question is about finding the longest _non-contiguous_ sequences, which is a much harder problem than the OP is trying to solve here. — abarnert, Jun 12 '18 at 23:23

Nick Cipriano · Answer 1 · 2018-06-12T23:07:43.330

1

Your code doesn't really make any sense for what you need to do. Your code will only find the longest substring in alphabetical order starting from index 0. Meaning when it reaches the end of the first longest substring 0 through whatever, it'll stop and won't look further.

s = 'vwjxxumjb'

count = 1
longest = 1
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) 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 = 1

start = end - longest + 1
"""
end is the last position in the longest string 
longest is length of the string 
so the end - longest characters = the start of string which is 
"""

print('Longest substring in alphabetical order is: ' + s[start:end + 1])
#prints the letters in s from position Start to End + 1 (+1 end does not include the index that it is given)

Edit: A complete answer to make Delirious Lettuce happy.

edited Jun 12 '18 at 23:07

answered Jun 12 '18 at 22:59

Nick Cipriano

43
6

Hint as an answer? – G_M Jun 12 '18 at 23:00
Yeah, you can tell he's learning so I don't want to do the work for him otherwise what is he learning? He's already on the right track. – Nick Cipriano Jun 12 '18 at 23:02
1

Why not just comment then? – G_M Jun 12 '18 at 23:02
I must have 50 reputation to comment on a question. – Nick Cipriano Jun 12 '18 at 23:03
I don't see anything inherently wrong with something like this as an answer. Not every answer needs to be spoonfed. – user3483203 Jun 12 '18 at 23:04
1

@user3483203 the way i see it, it's because it's not an answer. it's a hint. if you're pointing someone in a general direction to solve their problem, but aren't actually providing an answer, then it isn't an answer. i agree that it should be a comment, or the answer needs to be edited to be an actual answer. – crookedleaf Jun 12 '18 at 23:07
The question is very unclear. He answered why the current code doesn't work, and showed which part of the current code to correct. I don't see how that's not an answer. – user3483203 Jun 12 '18 at 23:10
My answer has been fixed to be the exact answer to his homework, cheers! – Nick Cipriano Jun 12 '18 at 23:11
1

I think a hint can be a good answer. However, I'm not sure this answer does a very good job, because it changes a bunch of stuff that isn't relevant to the problem. Why keep track of a count and three indexes, when what the OP was doing with keeping two strings and comparing `len` was fine? Sure, this is a little more efficient, but it's hardly likely to matter here, and I think it's less readable and easier to make off-by-one errors this way. But, more importantly, it's different from the code the OP almost got right and presumably already understands. – abarnert Jun 12 '18 at 23:21

abarnert · Accepted Answer · 2018-06-12T23:18:44.867

The easiest way to see your problem is to step through the code. You can do this with the builtin debugger that comes with Python (or the nice graphical one that comes with your IDE, if you use one), or just by adding a mess of print statements. But for something as small as this problem, you can use an online visualizer, like this one.

At first, everything seems to go well. It sees that vw is longer than v and remembers that. It sees that j >= w is false so it starts over with j.

But then, at step 16, you've got longest = 'vw', current = 'jx', and len(current) > len(longest) is false, so you hit the else and set current = 'x'. And then, at step 21, with current = 'xx', you again hit the else and set current = 'x'. And that's where it's going wrong.

Obviously, what you want to do here is not set current = c every time current is shorter than longest, but only when c >= current[-1] is false. Which is really just a matter of trivially rearranging your if/if/else logic. (The smallest change is to indent the second if, but I think it may make more sense to move the else up to where it's supposed to be, like this.)

While we're at it, you should try to come up with examples that could break your code, and then running them all through the visualizer/debugger/print-fiesta. Building a suite of unit tests to run is worth doing, even if you haven't yet gotten to the point where you know how to wrap your code in functions and use a unit test framework.

FInding longest substring in abc order

2 Answers2