<p>Given a string <code>s</code> and a string array <code>dictionary</code>, return <em>the longest string in the dictionary that can be formed by deleting some of the given string characters</em>. If there is more than one possible result, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.</p>

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

<pre>
<strong>Input:</strong> s = &quot;abpcplea&quot;, dictionary = [&quot;ale&quot;,&quot;apple&quot;,&quot;monkey&quot;,&quot;plea&quot;]
<strong>Output:</strong> &quot;apple&quot;
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;abpcplea&quot;, dictionary = [&quot;a&quot;,&quot;b&quot;,&quot;c&quot;]
<strong>Output:</strong> &quot;a&quot;
</pre>

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

<ul>
	<li><code>1 &lt;= s.length &lt;= 1000</code></li>
	<li><code>1 &lt;= dictionary.length &lt;= 1000</code></li>
	<li><code>1 &lt;= dictionary[i].length &lt;= 1000</code></li>
	<li><code>s</code> and <code>dictionary[i]</code> consist of lowercase English letters.</li>
</ul>

class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        
        int n = s.size();

        vector<int> occ(n);

        unordered_map<char, int> mp;

        for(int i=n-1; i>=0; i--)
        {
            if(mp.find(s[i])==mp.end())
            {
                mp[s[i]]=i;
                occ[i]=n;
            }
            else
            {
                occ[i]=mp[s[i]];
                mp[s[i]]=i;
            }
        }

        for(int i=0; i<n; i++)
        {
            cout<<occ[i]<<", ";
        }cout<<endl;

        for(auto i: mp)
        {
            cout<<i.first<<" : "<<i.second<<endl;
        }cout<<endl;

        vector<string> ans;
        int mx=0;

        string res;

        for(auto str: dictionary)
        {
            unordered_map<char, int> mp1 = mp;
            vector<int> occ1 = occ;

            int m = str.size();

            int last = n;

            int flag=m;

            for(int i=m-1; i>=0; i--)
            {
                if(mp1.find(str[i])!=mp1.end())
                {
                    int curr = mp1[str[i]];
                    int temp = -1;

                    while(curr < last)
                    {
                        temp = curr;
                        curr = occ1[curr];
                    }

                    if(temp==-1)
                    {
                        break;
                    }

                    last = temp;
                }
                else
                {
                    break;
                }

                flag = i;
            }

            if(flag==0)
            {
                cout<<str<<endl;
                ans.push_back(str);
                int sz = str.size();
                mx = max(mx, sz);

                if(str.size()==mx)
                {
                    res = str;
                }
            }
        }

        cout<<"mx is "<<mx<<endl;

        for(string str: ans)
        {
            if(str.size()==mx)
            {
                res = min(res, str);
            }
        }

        return res;
    }
};
34274