## Sunday, March 5, 2017

### HackerRank - Super Reduced String

Problem:

Analysis:

The problem hinted at the solution - it asked for 'the' final string. It means that there exists a unique final string, which means it doesn't matter how we order the reductions, at the end of the day, the end result is the same.

My first thought is that let's scan the string once and remove the adjacent duplicates, but that by itself is not correct as

'abba' will simply become 'aa' which should be further reduced into an empty string.

Repeatedly doing that until the string cannot be reduced work, but it works at a cost of quadratic time. As can be seen in the case

'abc...xyzzyx...cba' => Empty string

Solution:

The above should hint us on having a stack. We push on the stack as we go, and whenever we see adjacent identical element, we pop both. That allow us to 'super reduce' on the fly.

Another trick I done in the code is that I scan the string from right to left, that allow us to just pop the answer out because the stack help us to reverse it back again.

Performance wise, it is obviously linear, and is apparently optimal.

Code：

#include "stdafx.h"

#include <iostream>
#include <stack>
#include <string>
using namespace std;

// https://www.hackerrank.com/challenges/reduced-string

#include "HACKER_RANK_SUPER_REDUCED_STRING.h"

int HACKER_RANK_SUPER_REDUCED_STRING()
{
stack<char> seen;
string s;
cin >> s;
for (int i = 0; i < s.size(); i++)
{
char c = s[s.size() - 1 - i];
if (seen.size() > 0 && seen.top() == c)
{
seen.pop();
}
else
{
seen.push(c);
}
}
if (seen.size() > 0)
{
while (seen.size() > 0)
{
cout << seen.top();
seen.pop();
}
}
else
{
cout << "Empty String";
}
return 0;
}