Find Strings Interview Street Problem

Problem details are here

Following is my solution , This is n-squared solution and will not be accepted by Robot. Need to come up with something smart and faster solution.

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

/* Simple O(n2) Solution */

std::vector<std::string> S;

void solve() {
    size_t Qi = 0;
    std::cin >> Qi;

    if ( S.size() < Qi - 1 ) {
        std::cout << "INVALID" << std::endl;
    } else {
        std::cout << S[Qi - 1] << std::endl;
    }
}
void get_unique_sub_string(std::string &str, std::vector<std::string> &sTemp) {
    size_t length = str.size();
    for( size_t i = 0 ; i < length ; i++ ) {
        for( size_t j = 1 ; j <= length - i ; j++ ) {
            sTemp.push_back(str.substr(i, i + j));
        }
    }
    std::sort(sTemp.begin(), sTemp.end());
    sTemp.erase(std::unique(sTemp.begin(), sTemp.end()), sTemp.end());
}
int main ( int argc, char **argv ) {
    int n; // number of strings
    std::cin >> n;
    for ( int i = 0; i < n ; i++){
        // Read the string
        std::string str;
        std::cin >> str;

        std::vector<std::string> sTemp;
        get_unique_sub_string(str,sTemp);

        std::vector<std::string> Stemp_result;
        Stemp_result.resize (sTemp.size() + S.size());

        std::set_union(sTemp.begin(), sTemp.end(), S.begin(), S.end(), Stemp_result.begin());
        S = Stemp_result;

    }
    std::vector<std::string>::iterator it = std::remove_if(S.begin(), S.end(),std::mem_fun_ref(&std::string::empty));
    S.erase(it, S.end());

    int q; // number of queries
    std::cin >> q;
    for ( int i = 0; i < q; i++) {
        solve();
    }
    return 0;
}
Advertisements

One thought on “Find Strings Interview Street Problem

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s