I need to code this, but facing problem

This is the place for queries that don't fit in any of the other categories.

I need to code this, but facing problem

Postby rahul_2008aust » Sat Oct 26, 2013 10:31 pm

I have to write a program that prints the longest substring of s in which the letters occur in alphabetical order. For example, if s = 'azcbobobegghakl', then my program should print.... 'beggh'

I have coded this problem. But output shows a error for this. It is actually my fault to save the strings not in a correct order.
Here is my code.

Code: Select all
s= 'azcbobobegghakl'
sstore=''
new=''
for i in range(len(s)-1):
    if s[i]<s[i+1]:
        new+=s[i]
        if s[i]<s[i+1]:
            new+=s[i+1]
        else:
            new
    else:
        if len(new)>len(sstore):
            sstore=new
        else:
            new=''
print 'Longest substring in alphabetical order is:',sstore


Please someone could come forward and help me.
Last edited by micseydel on Sat Oct 26, 2013 10:53 pm, edited 1 time in total.
Reason: Code tags, lock.
rahul_2008aust
 
Posts: 2
Joined: Sat Oct 26, 2013 10:20 pm

Re: I need to code this, but facing problem

Postby micseydel » Sat Oct 26, 2013 10:59 pm

Hello, and welcome to the forum! Please read this before making another post, and be sure to follow it's direction about including your full traceback for the error you're getting (in code tags please!).

I see you're using indexes, which is probably the traditional way to do this problem, but it's error prone and humans are bad at it. Here's a hint to try to clean up your code a bit.

Code: Select all
>>> s= 'azcbobobegghakl'
>>> for left, right in zip(s, s[1:]):
   print left, right

   
a z
z c
c b
b o
o b
b o
o b
b e
e g
g g
g h
h a
a k
k l

(This code has some memory scaling issues for large inputs, but so does your code so I figured it's probably not an issue. If it is, feel free to let us know.)
Join the #python-forum IRC channel on irc.freenode.net!

Please do not PM members regarding questions which are meant to be discussed publicly. The point of the forum is so that others can benefit from it. We don't want to help you over PMs or emails.
User avatar
micseydel
 
Posts: 1354
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA

Re: I need to code this, but facing problem

Postby rahul_2008aust » Sat Oct 26, 2013 11:15 pm

Thanks for your prompt reply. But may be you have not understand my issue.
I have to print the longest string that is in alphabetical order. that means if I have a string say, s='azcbobobegghakl'. Then my output should show 'beggh'.
And I have to do it without using library functions. Only can use loops and comparison operators. My code has a bug where it only shows 'e' two times. Can
you please help me with that? What modications should I need?
rahul_2008aust
 
Posts: 2
Joined: Sat Oct 26, 2013 10:20 pm

Re: I need to code this, but facing problem

Postby ochichinyezaboombwa » Mon Oct 28, 2013 11:26 pm

I am confused why did you do it twice:
Code: Select all
    if s[i]<s[i+1]:
        new+=s[i]
        if s[i]<s[i+1]:
            new+=s[i+1]
and what is this mysterious code
Code: Select all
        else:
            new
supposed to do?

Anyhow: this is a very popular CS task ("longest increasing sequence" or "longest non-decreasing sequence"). I recommend to throw your code away and start afresh with clear design. Here are some ideas:

(@ mucseydel : I am actually more comfortable with indexes so I will do it with indexes).

So the goal is to find such indexes a,b into string s such that s[a:b+1] is the longest non-decreasing / increasing sequence. (Whether we'll finf non-decreasing or strictly increasing is the minor detail and will only depend on whether you use operator "<=" or "<" while comparing elements). OK.

a) consider that the answer is (0,0) : that is, the 1st symbol is the answer: nothing longer than that exists; -- assign it to some vars, like
Code: Select all
i,j = 0,0


b) go over all chars of s between 1st and and next-to-last:
Code: Select all
for k in range(0, len(s)-1):
    ...


c) if the character after k is greater (or >=) than the kth, we're increasing:
good, increase your j;

d) otherwise:
stopped increasing;
your current (i,j) might be the answer.
You also need to have another tuple (say (a,b) to keep the current longest substring: create is before the loop similar to i,j.
Now, if (b-a) < (j-i): you've found another maximum; store it in (a,b);
in any case, reset (i,j) to (k+1, k+1)

Try to implement it; don't hesitate to ask more questions if you're stuck.

NB: there is a corner-case... Let it surprise you.

Finally, here is how I would test it:
Code: Select all
    ss = [
        ("azcbobobeghakl", "begh" ),
        ("azcbobobegghakl", "beg" ),
        ("abcdeabcdefg", "abcdefg" ),
        ("abcdeabcdefga", "abcdefg" ),
        ("zyx", "z" ),
        ("zyxa", "z" ),
        ("zyxab", "ab"),
        ("a", "a" ),
        ("", "" ),
        ]
    for s, expected in ss:
        ans = longest_increasing_sequence(s)
        print repr(s), repr(ans), ans == expected
        assert(ans == expected)

ochichinyezaboombwa
 
Posts: 200
Joined: Tue Jun 04, 2013 7:53 pm


Return to General Coding Help

Who is online

Users browsing this forum: mullit1986 and 4 guests