# My AC approach using sorting and binary search

• Approach:

1. Sort the strings in descending order of length (if length is equal, opt for the lexicographically smaller one)

2. Pre-process the string `s` into a dictionary of char to list of indices. Note that these indices are in sorted order and can therefore facilitate the use of binary search.

Overall Time complexity for N strings of average length |T| and string of length |S| :O(NlogN) + O(NTlog(|S|)

``````class Solution {
public:
struct order
{
bool operator()(const string& s1, const string& s2)
{
if(s1.size() == s2.size())
{
int j = 0;
while(s1[j] == s2[j] && j < s1.size())
j++;
return (j == s1.size()) ? true : s1[j] < s2[j];
}
else
return s1.size() > s2.size();
}
};
string findLongestWord(string s, vector<string>& d)
{
sort(d.begin(), d.end(), order());
vector<vector<int>> dict(26, vector<int>());
int i = 0;
for(auto c : s)
dict[c - 'a'].push_back(i++);
string result;
for(auto ele : d)
{
int id = 0;
bool notPossible = false;
for(auto c : ele)
{
auto nextIt = lower_bound(dict[c - 'a'].begin(), dict[c - 'a'].end(), id);
if(nextIt == dict[c - 'a'].end())
{
notPossible = true;
break;
}
id = *nextIt + 1;
}
if(!notPossible)
{
result = ele;
break;
}
}
return result;
}
};
``````

• I think the overall complexity of N strings is O(N^2*log|S|)

• @moan1223 thanks, fixed it.

• Shorter one with same approach binary search:

``````bool comp(string &a, string &b) {
if (a.size()==b.size()) return a.compare(b)<0;
return a.size()>=b.size();
}

class Solution {
public:
string findLongestWord(string s, vector<string>& d) {
string res;

vector<vector<int>> index(26);
for(int i=0; i<s.size(); ++i) index[s[i]-'a'].push_back(i);

for(auto &t : d) {
if (ok(t, index)) {
if (res.empty()||comp(t,res)) res = t;
}
}

return res;
}

bool ok(string t, vector<vector<int>> &index) {
int cur = -1;
for(char &c : t) {
auto is = index[c-'a'];
auto i = upper_bound(is.begin(), is.end(), cur);
if (i==is.end()) return false;
cur = *i;
}

return true;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.