<p>You are given two string arrays <code>words1</code> and <code>words2</code>.</p>

<p>A string <code>b</code> is a <strong>subset</strong> of string <code>a</code> if every letter in <code>b</code> occurs in <code>a</code> including multiplicity.</p>

<ul>
	<li>For example, <code>&quot;wrr&quot;</code> is a subset of <code>&quot;warrior&quot;</code> but is not a subset of <code>&quot;world&quot;</code>.</li>
</ul>

<p>A string <code>a</code> from <code>words1</code> is <strong>universal</strong> if for every string <code>b</code> in <code>words2</code>, <code>b</code> is a subset of <code>a</code>.</p>

<p>Return an array of all the <strong>universal</strong> strings in <code>words1</code>. You may return the answer in <strong>any order</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> words1 = [&quot;amazon&quot;,&quot;apple&quot;,&quot;facebook&quot;,&quot;google&quot;,&quot;leetcode&quot;], words2 = [&quot;e&quot;,&quot;o&quot;]
<strong>Output:</strong> [&quot;facebook&quot;,&quot;google&quot;,&quot;leetcode&quot;]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> words1 = [&quot;amazon&quot;,&quot;apple&quot;,&quot;facebook&quot;,&quot;google&quot;,&quot;leetcode&quot;], words2 = [&quot;l&quot;,&quot;e&quot;]
<strong>Output:</strong> [&quot;apple&quot;,&quot;google&quot;,&quot;leetcode&quot;]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= words1.length, words2.length &lt;= 10<sup>4</sup></code></li>
	<li><code>1 &lt;= words1[i].length, words2[i].length &lt;= 10</code></li>
	<li><code>words1[i]</code> and <code>words2[i]</code> consist only of lowercase English letters.</li>
	<li>All the strings of <code>words1</code> are <strong>unique</strong>.</li>
</ul>

class Solution {
private:
    class list_node {
    public:
        list_node *prev;
        list_node *next;

        list_node() {
            prev = next = nullptr;
        }
    };

    class list_head {
    public:
        list_node *head;
        list_node *tail;

        list_head() {
            head = tail = nullptr;
        }

        void insert_after(list_node *prev, list_node *first, list_node *last) {
            if (prev == nullptr) {
                last->next = head;
                head = first;
            } else {
                last->next = prev->next;
                prev->next = first;
            }
            first->prev = prev;
            if (last->next == nullptr)
                tail = last;
            else
                last->next->prev = last;
        }

        void erase(list_node *first, list_node *last) {
            if (first->prev == nullptr)
                head = last->next;
            else
                first->prev->next = last->next;
            if (last->next == nullptr)
                tail = first->prev;
            else
                last->next->prev = first->prev;
            first->prev = last->next = nullptr;
        }
    };

    class entry {
    public:
        int         freq;
        list_node   *n;

        entry() {
            freq = 0;
        }
    };

public:
    vector<string> wordSubsets(vector<string>& words1, vector<string>& words2) {
        char c;
        int i, j;
        int idx;
        int len;
        int n;
        int val;
        list_head rem, tmp;
        list_node *node1, *node2;
        vector<entry> frequencies;
        vector<string> res;

        frequencies.resize(26);

        n = words2.size();

        for (i = 0; i < n; i++) {
            string& word = words2[i];
            vector<int> freq;

            freq.resize(26);

            len = word.length();
            for (j = 0; j < len; j++) {
                c = word[j];
                idx = c - 'a';
                val = ++freq[idx];
                if (val > frequencies[idx].freq) {
                    if (frequencies[idx].freq == 0) {
                        node1 = new list_node();
                        frequencies[idx].n = node1;
                        rem.insert_after(rem.tail, node1, node1);
                    }
                    frequencies[idx].freq = val;
                }
            }
        }

        n = words1.size();

        for (i = 0; i < n; i++) {
            string& word = words1[i];
            vector<int> freq;

            freq.resize(26);

            len = word.length();
            for (j = 0; j < len; j++) {
                c = word[j];
                idx = c - 'a';
                val = ++freq[idx];
                if (val == frequencies[idx].freq) {
                    node1 = frequencies[idx].n;
                    rem.erase(node1, node1);
                    tmp.insert_after(tmp.tail, node1, node1);
                }
            }

            if (rem.head == nullptr)
                res.push_back(word);

            if (tmp.tail != nullptr) {
                node1 = tmp.head;
                node2 = tmp.tail;
                tmp.erase(node1, node2);
                rem.insert_after(rem.tail, node1, node2);
            }
        }

        return res;
    }
};
106400