bbg-Eq: longest abbreviation #easier

Given a long word with N non-unique characters, we know there can be 2^N abbreviations (including the original word, and including the empty string).

Requirement: I give you a list of strings and you suspect some of them could be an abbreviation of your word. Find the longest string among them that’s a valid abbreviation. Optimize for time complexity.

I feel this problem appears simple but not easy to complete quickly

https://github.com/tiger40490/repo1/blob/py1/py/str/testAbbr_ez.py is my python solution, different from the c++ solution below. Not sure which has more bugs.

I started with string::find() and hit the problem of non-unique characters. Interviewer hinted char-matching — the key point I needed for this type of problem.

```#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

typedef string candidate;

vector<candidate> v{"monkey","aaaaaaaaaaaaaaaaaa", "mamalon", "monk"};
string const haystack{"mamalonkey"};
size_t hsize=haystack.size();

//Tip: can use typdef alias in argument:)
bool lenComp(candidate const & a, candidate const & b){
return a.size()<=b.size();
}
ostream & operator<<(ostream & os, vector<candidate> const & c){
size_t const sz = c.size();
for (int i=0;i<sz; ++i){
os<<c[i]<<" ";
}
os<<endl; return os; } //single-pass 🙂
}

bool check1candate(candidate const & c){
if (c.size() > hsize) return false;

for(int i=0, h=0; h<hsize; ++h){
if (c[i] == haystack[h]){
if (i==c.size()-1) return true;
++i;
}
}
return false;
}
int main(){
sort(v.begin(), v.end(), lenComp);
cout<<v; for (int i=v.size()-1; i>=0; --i){
if (check1candate(v[i])){
cout<<"winner is "<<v[i];
return 0;
}
}
}
```