AP
BAN USERIf there is an efficient algorithm for this problem I doubt it can be devised during the interview. Dynamic programming doesn't really work here because the problem doesn't separate into independent subproblems (the singleton letters must be taken so you can vary only what is between). All people claiming linear algorithms here just didn't give a good thought to testing them. So, I'll stick to the correctly working algorithm that can be realistically coded in 1/2 hour. It is exponential, but there is significant optimization through pruning.
string getSmallest(const string &s, unordered_map<char, queue<int>> &M, int start)
{
int n = start;
while ((n < s.size()) && (M.find(s[n]) == M.end())) // Skip the ones that already taken
n++;
if (n == s.size())
return "";
string incl;
string excl;
char c = s[n];
unordered_map<char,queue<int>> Mc(M);
queue<int> q(Mc[c]);
Mc.erase(c);
incl.push_back(c);
incl += getSmallest(s, Mc, n + 1);
if (q.size() > 1)
{
q.pop();
Mc[c] = q;
excl = getSmallest(s, Mc, n + 1);
}
if (excl.empty() || incl.compare(excl) < 0)
{
return incl;
}
return excl;
}
string removeDuplicatesToGetLexMinimum(const string &s)
{
string res;
unordered_map<char, queue<int>> M;
for (int i = 0; i < s.size(); i++)
{
char c = s[i];
M[c].push(i);
}
res = getSmallest(s, M, 0);
return res;
}
void testStringTransformation()
{
string s = "ecbafcdcbc";
string r = removeDuplicatesToGetLexMinimum(s);
cout << "Transforming a string:\n";
cout << s << " " << r << endl;
s = "cacasc";
r = removeDuplicatesToGetLexMinimum(s);
cout << s << " " << r << endl;
s = "abcadaba";
r = removeDuplicatesToGetLexMinimum(s);
cout << s << " " << r << endl;
}
A working algorithm. Basically, the idea is as follows.:
- Push every node on the stack along with its index in parent's array and move to the leftmost child (or null)
- When encounter null then peek the stack and handle two cases - there are siblings on the right or there aren't (in which case print)
- AP September 21, 2015