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.

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. — user76299
– user76299, Commented Jun 22, 2015 at 16:14

SylvainD · Accepted Answer · 2017-10-09 11:33:31Z

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.

s[i] >= s[i - 1] will throw an exception for the first character in string! — Quest
– Quest, Commented Oct 3, 2017 at 8:06
@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... — SylvainD
– SylvainD, Commented Oct 9, 2017 at 11:32
To be honest with you, I actually used your code with a few changes myself and it worked great for all test cases. — Quest
– Quest, Commented Oct 10, 2017 at 21:51

mdfst13 · Accepted Answer · 2015-06-22 20:51:19Z

        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.

Stack Exchange Network

Find largest substring in alphabetical order in a given string

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Find largest substring in alphabetical order in a given string

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions