Click here to Skip to main content
15,884,628 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
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.


What I have tried:

I couldn't have any idea on how to begin this exercise.
Posted
Updated 7-Feb-23 23:42pm
v2

Conceptually, use two indices, e.g. b (for 'begin') and e (for 'end').
Start with b=0, e=b+1 and check if s[e]>=s[e-1]:
  • if the condition holds, then increment b and repeat the check.
  • On the other hand, if the condition is not true, then you have found the length of the current subtring, namely (e-b), if it is the longest so far then store current 'begin' and 'end' (say max_b = b, max_e = e). In any case restart with b = e, e = b+1.

Of course, in the actual implementation, you have also to handle the end of the string.
 
Share this answer
 
Think about how you would do it manually.

You would look at the first character in the string, and compare it with the next. If they are in alphabetical order, you'd add one to a mental count and look at the next pair.
If they weren't, you'd compare the current count with the "longest count" and if it is greater then you have found a longer string, so it becomes the new longest substring.
When you set a new substring, you save the start position as well.

When you get to the end, you know the first longest substring. Try it on paper and you'll see what I mean.
Now look at what you needed to "remember" to do it manually, and think about what variables you will need to hold that, and what the rules are. Now you can start coding to do the same job.

If you are having problems getting started at all, then this may help: How to Write Code to Solve a Problem, A Beginner's Guide[^]
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900