Find largest substring in alphabetical order in a given string

Question

#include<iostream>
#include<string>
using namespace std;
int main()
{
 string s, sub;
 cin >> s;
 int check = 1, count = 0, pos = 0; // keeping count of number of alphabetical ordered substring characters
 int i = 1; // loop variable
 int prev = 0; //to hold previous value of loop variable
 while (i< s.size())
 {
 check = 1;
 while ((int)s[i] >= (int)s[i - 1])
 {
 ++check;
 ++i;
 }
 if (check > count)
 {
 count = check;
 pos = i - check;
 }
 if (i == prev)
 ++i;
 prev = i; //if the inner while loop isn't executed, then i will be incremented here
 }
 cout << "Longest substring in alphabetical order is :" << s.substr(pos, count) << endl;
}

This was a part of my assignment. I could solve this in 10 minutes but I am not sure if this is a very efficient code. Though a (if any) more efficient algorithm exists for this, it may not make much of a different but I am keen on making all my programs as efficient as possible right from beginning.

• user76299: Yes, there is a better option, and you are close to it. I remember this problem from my algorithm homework. Since this is for an assignment, I don't want to give away the answer. Finding out on your own will solidify it. However, (if my memory holds up) the solution involves using the hashcode function.

Answer 1

Here are a few details :

Variable declaration

It is usually a good idea to move your variable declaration in the smallest possible scope as close as possible to where they are getting used.

This for instance shows that sub is never used.

Also, you can take this chance to change your while loop into a for loop and declare i in it.

Warnings

It is a good thing to activate all warnings. For instance, I get :

warning: comparison between signed and unsigned integer expressions [-Wsign-compare]

Simplifying things

Instead of messing with prev, you can detect if i has been increased already by considering the value of check.

Cast

I do not think these casts are useful.

Length

It could be a good idea to store the length of the string in a variable not to retrieve it at every iteration.

Using namespace

using namespace is sometimes frowned upon.

At this stage the code looks like :

#include <iostream>
#include <string>
int main()
{
 std::string s = "vjvdfkjckvjkjrdsfjsdkjfliureyqnbcxvfjhdeiutogfvjdsvkdfcdcoivjriofdjsrs";
// std::cin >> s;
 int count = 0, pos = 0; // keeping count of number of alphabetical ordered substring characters
 for (size_t i = 1, len = s.size() ; i < len ; )
 {
 int check = 1;
 while (s[i] >= s[i - 1])
 {
 ++check;
 ++i;
 }
 if (check > count)
 {
 count = check;
 pos = i - check;
 }
 if (check == 1)
 ++i;
 }
 std::cout << "Longest substring in alphabetical order is :" << s.substr(pos, count) << std::endl;
}

Algorithmic trick

A trick could be to say that if you have a current result of length n, you don't care about any substring of length m < n. Thus, you can check backward from position i + n : as long as it is in descending order, you continue, otherwise, it gives you a starting position to start again.

I am not sure if this is really clear. I'll tr to improve asap.

• Quest: s[i] >= s[i - 1] will throw an exception for the first character in string!
• SylvainD: @Quest this seems pretty bad indeed. I don't know how I missed it :-( Also, the more I look at it, the more I have a feeling that many other errors are in my code...
• Quest: To be honest with you, I actually used your code with a few changes myself and it worked great for all test cases.

Answer 2

 while ((int)s[i] >= (int)s[i - 1])

What happens if the entire string is in alphabetical order? You should check that i isn't greater than the string length on every iteration of the inner loop too. Or replace the inner loop.

 int count = 1, maxCount = 0, position = 0; // keeping count of number of alphabetical ordered substring characters
 for (size_t i = 1, length = s.size(); i < length ; ++i)
 {
 if (s[i] < s[i - 1])
 {
 if (count > maxCount)
 {
 maxCount = count;
 position = i - count;
 }
 count = 0;
 }
 ++count;
 }
 if (count > maxCount)
 {
 maxCount = count;
 position = s.size() - count - 1;
 }

By changing from a while true to an if false, we don't need the prev variable or to compare i and check. We do need to do the extra check against the maximum in case the final sequence is the longest.