CODEWITHSUNDEEP
c++string
CodingKingggg
CodingKingggg

Reputation: 73

A program about Largest Subsequence of string

The question I have is called "Largest Subsequence". Here is the guideline.

A subsequence of a string x can be made by erasing some (possibly all or none) of the letters in x. For example, "opt" is a subsequence of "computer", while "rt" is not. Now, we want to find the lexicographical largest subsequence from a given string. For example, the sorted subsequences of “test” are: "" (empty string), "e", "es", "est", "et", "s", "st", "t", "te", "tes", "test", "tet", "ts", "tst" and "tt". And “tt” is the largest subsequences here, so print it out.

I had finished my code(shown below). It succeeded in my local compiler but failed when handed in (runtime error)

#include <queue>
#include <iostream>
#include <string>
using namespace std;
char largest(string s) {
    char c = 'a';
    for (int i = 0; i < s.length(); i++) {
        if (s.at(i) > c) {
            c = s.at(i);
        }
    }
    return c;
}
string eraseStr(string s, char c) {
    for (int i = 0; i < s.length(); i++) {
        if (c == s.at(i)) {
            s = s.substr(i + 1, s.length());
            return s;
        }
    }
}
string out(string s, char c) {
    if (s.size() == 1 || s.size()== 0) {
        return s;
    }
    else {
        string str = eraseStr(s, largest(s));
        cout << largest(s);
        return out( str, largest(str));
    }
}
int main() {
    string s[100];
    int numCase;
    cin >> numCase;
    for (int i = 0; i < numCase; i++) {
        cin >> s[i];
        cout<<out(s[i], largest(s[i]))<<endl;
    }                                     
    return 0;
}

Hope to have a solution/reason. Thanks a lot for help.

Upvotes: 1

Views: 243

Answers (2)

Damien
Damien

Reputation: 4854

If you have a run time error, it is likely that the algorithm must be improved.

This is a O(nlogn) solution

    1. sort (in a stable way) indices according to string values
    2. first character corresponds to first index
    3. add following characters, if the index is greater than last index selected

And the programme:

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

    //  1. sort (in a stable way) indices according to string values
    //  2. first character corresponds to first index
    //  3. add following characters, if the index is greater than last index selected

    std::string max_subsequence (std::string &x) {
        std::string result;
        if (x.size() == 0) return result;

        std::vector<int> index (x.size());
        std::iota (index.begin(), index.end(), 0);
        std::stable_sort (index.begin(), index.end(), [&] (int i, int j) {return x[i] > x[j];});

        result.push_back(x[index[0]]);
        int last_index = index[0];
        for (int i = 1; i < x.size(); ++i) {
            if (index[i] > last_index) {
                result.push_back(x[index[i]]);
                last_index = index[i];
            }
        }
        return result;
    }

    int main() {
        std::string s = "test";
        auto result = max_subsequence (s);

        std::cout << "result = " << result << "\n";
        return 0;
    }

Upvotes: 1

darune
darune

Reputation: 10962

Possible runtime error on this line:

cin >> s[i];

segfault is possible if i >= 100. You would need to dynamicly allocate here - I suggest you learn about std::vector, eg. you could do

int main() {

    int numCase;
    cin >> numCase;
    std::vector<string> s(numCase);
    for (int i = 0; i < numCase; i++) {
        cin >> s[i];
//...

There could be other runtime errors, this was just the first one I spottet.

Upvotes: 0

Related Questions