1

I am trying to write a python program that will take any string of lowercase letters and return the longest alphabetical substring within it. Below is a segment of the code. 

s="abc"                                            #sample string
anslist=[]                                         #stores answers
shift=0                                            #shifts substring
expan=0                                            #expands substring
while len(s) >= 1+shift+expan:                     #within bounds of s
    if s[0+shift+expan] > s[1+shift+expan]:        #if not alphabetical
        shift += 1                                 #moves substring over
    else:                                          #if alphabetical
        while s[0+shift+expan] <= s[1+shift+expan]:  #while alphabetical
            expan += 1                               #checks next letter
        anslist += s[0+shift:2+shift+expan]       #adds substring to ans
        expan = 0                                  #resets expansion

When I run the code, the line containing while s[0+shift+expan] <= s[1+shift+expan]: creates an error that the string index is outside of the range. I see that adding to expan will put the index out of range, but shouldn't the largest while loop solve this? I appreciate any help.

Improve this question
7
  • There's a good chance this is an off by one error. Shouldn't the while condition be len(s) > 1+shift+expan since len will be 1 greater than the last 0 based index? Commented Jun 8, 2017 at 19:15
  • @0101001101000010 That won't fix the error it'll still be out of bounds. s has a len of 3 but you can only index it up to 2 since the maximum index is len(object) - 1 and shift + expan > 0. Commented Jun 8, 2017 at 19:15
  • s[0+shift+expan] <= s[1+shift+expan] is true for b and c so then expan is +=1 and that goes out of range, you should add a check like and expand+1+1+shift<len(s) Commented Jun 8, 2017 at 19:15
  • @Djokester is the first sentence in his post unclear? Seems perfectly fine to me... Commented Jun 8, 2017 at 19:16
  • I am more interested in learning what is causing the error in the above code than creating another program that works. I still don't quite understand how to fix the while loop issue. Commented Jun 8, 2017 at 19:45

2 Answers 2

Reset to default
1

First, why your code doesn't work:

  • You aren't protecting your inner loop against running off the end of the string
  • your indexes are off when "saving" the substring
  • you += onto anslist, which is not how you add strings to a list
  • you don't increment the shift after processing a substring, so when it clears expan it starts over at the same index and loops forever

Fixed code (inline comments explain changes):

s="abckdefghacbde"                                 #sample string
anslist=[]                                         #stores answers
shift=0                                            #shifts substring
expan=0                                            #expands substring
while len(s) > 1+shift+expan:                      #within bounds of s
    if s[0+shift+expan] > s[1+shift+expan]:        #if not alphabetical
        shift += 1                                 #moves substring over
    else:                                          #if alphabetical
        # Added guard for end of string
        while len(s) > 1 + shift + expan and       # While still valid
              s[0+shift+expan] <= s[1+shift+expan]:# While alphabetical
            expan += 1                             #checks next letter
        # Fixed string sublength and append instead of +=
        anslist.append(s[0+shift:1+shift+expan])   #adds substring to ans
        # Continue to next possible substring
        shift += expan                             # skip inner substrings
        expan = 0  
print anslist

Results in:

['abck', 'defgh', 'ac', 'bde']

So the last step would be to find the one with the longest length, which I'll leave up to you, since this looks like homework.

To answer the question:

I see that adding to expan will put the index out of range, but shouldn't the largest while loop solve this?

It protects against your starting substring index from going off, but not your expansion. You must protect against both possibilities.

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

2 Comments

I've been working on this code for two days, and it's great to finally find what the mistake(s) were. Thank you so much for the detailed response and also for the help of everybody who contributed to this question!
@GradyMorrissey In the future, please include the stack trace, as it makes it easier to identify the specific issue. Also, I would suggest taking a peek at PEP-8, as there are some significant style issues which make your code hard to read. That being said, don't be discouraged. Everyone makes mistakes.
0

Have a look at this. 

>>> import re
>>> words = []
>>> word = r'[a]*[b]*[c]*[d]*[e]*[f]*[g]*[h]*[i]*[j]*[k]*[l]*[m]*[n]*[o]*[q]*[r]*[s]*[t]*[u]*[v]*[x]*[y]*[z]*' # regex that would match sub-strings. Just extend it up to z. 
>>> string = "bacde"
>>> for m in re.finditer(word, string):
...         words.append(m.group())
>>> print(words) # list of substrings
['b', 'acde']

Then you can extract the largest string from the list of strings 

>>> print(max(words, key=len))
acde
Improve this answer

4 Comments

I think he wants alphabetical like "abc" or "def", not just alphabetic characters.
See he said alphabetical sub-string. I commented that it is unclear as to what he wants. He should give an expected output just abc doesnt make the cut!
@Djokester Sorry for the confusion. For s="abc" the expected output is "abc". Similarly, for s="bac" the expected output is "ac".
@GradyMorrissey has been edited to match your query. Just extend the regex pattern to z

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.