How to find the longest alphebetical substring c++

Question

I am trying to write a function that when given a string, it will return the longest substring that is sorted alphabetically. This has proven very difficult and despite many attempts I am no closer than when I began.

An example of what the function should do:

abacdefkabfhxy should return abcdefkxy abacdefkabfhixy should return abcdefhixy

Thanks for any help!

This is called the longest increasing subsequence problem: http://en.wikipedia.org/wiki/Longest_increasing_subsequence — Vincenzo Pii, Nov 15 '13 at 19:34
possible duplicate of [Find longest increasing sequence](http://stackoverflow.com/questions/4938833/find-longest-increasing-sequence) — Bernhard Barker, Nov 15 '13 at 19:46
And another one - [How to determine the longest increasing subsequence using dynamic programming?](http://stackoverflow.com/questions/2631726/how-to-determine-the-longest-increasing-subsequence-using-dynamic-programming) — Bernhard Barker, Nov 15 '13 at 19:48
And, for the record, generally speaking, a substring is not the same thing as a subsequence. Substrings are usually considered to be a contiguous subsequence. — twalberg, Nov 15 '13 at 20:03

score 0 · Answer 1 · answered Nov 15 '13 at 21:46

Try the following. It doesn't check if the characters are alphabetic, but you can easily add that condition yourself:

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <string>

std::string longest_alpha_substr(const std::string& str)
{
    char last = str[0];
    int size = 1;
    unsigned int i = 1;
    std::vector<std::pair<int, int>> pairs;

    for (; i < str.size(); ++i)
    {
        if (str[i] >= last)
        {
            last = str[i];
            ++size;
        } else
        {
            pairs.push_back(std::make_pair(i - size, size));
            size = 1;
            last = str[i];
        }
    }

    pairs.push_back(std::make_pair(i - size, size));

    using pair_type = std::pair<int, int>;

    auto max = std::max_element(pairs.begin(), pairs.end(),
                               [] (const pair_type& p1, const pair_type& p2)
    {
        return p1.second < p2.second;
    });

    return str.substr(max->first, max->second);
}

int main()
{
    std::string str = "ghijkdefghijabcde";
    std::cout << longest_alpha_substr(str); // "defghij"
}

score 0 · Answer 2 · answered Nov 16 '13 at 02:10

For each alphabet give values as a=1,b=2...z=26.

Now solve Longest Increasing sub sequence problem.

You will get a sequence of increasing numbers.

Convert them back to alphabets and you are done.

A[1..n] - input sequence L[j] = longest strictly increasing subsequence ending at position j

Recurrence eqn:

L[j] = max of i such that i<j & A[i] <A[j] {L[i]} + 1

How to find the longest alphebetical substring c++

2 Answers2