1772. Sort Features by Popularity

You are given a string array features where features[i] is a single word that represents the name of a feature of the latest product you are working on. You have made a survey where users have reported which features they like. You are given a string array responses, where each responses[i] is a string containing space-separated words.

The popularity of a feature is the number of responses[i] that contain the feature. You want to sort the features in non-increasing order by their popularity. If two features have the same popularity, order them by their original index in features. Notice that one response could contain the same feature multiple times; this feature is only counted once in its popularity.

Return the features in sorted order.

class Solution {
    string parse(string& s, int& p) {
        int n = s.length();
        string res = "";
        while(p < n and s[p] != ' ') {
            res.push_back(s[p++]);
        }
        p++;
        return res;
    }
    unordered_set<string> helper(string s) {
        int p = 0, n = s.length();
        unordered_set<string> res;
        while(p < n) {
            string token = parse(s, p);
            res.insert(token);
        }
        return res;
    }
public:
    vector<string> sortFeatures(vector<string>& A, vector<string>& R) {
        unordered_map<string, int> idmp;
        unordered_map<string, int> freq;
        for(int i = 0; i < A.size(); i++) {
            idmp[A[i]] = i;
            freq[A[i]] = 0;
        }
        for(auto& r : R) {
            for(auto& f : helper(r)) {
                if(idmp.count(f))
                    freq[f]++;
            }
        }
        vector<pair<int, int>> S;
        for(auto& a : A) {
            S.push_back({freq[a], idmp[a]});
        }
        
        sort(begin(S), end(S), [](auto& a, auto& b) {
            if(a.first == b.first) return a.second < b.second;
            return a.first > b.first;
        });
        
        vector<string> res;
        
        for(auto& [_, idx] : S) {
            res.push_back(A[idx]);
        }
        
        return res;
    }
};