Super Reduced String

See the original problem on HackerRank.

Solutions

A solution changes the string by removing same adjacent elements.

Here is a C++ implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

int main() 
{
    string S; cin >> S;
    
    auto finder = [&]{
        return adjacent_find(begin(S), end(S));
    };
    
	for (auto adjFind = finder(); adjFind != end(S); adjFind = finder())
	{	
		S.erase(adjFind, adjFind + 2);
	}
    cout << (S.empty() ? "Empty String" : S);
}

An alternative solution that does not modify the input uses an additional data structures:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <string>
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;

int main() 
{
    string S; cin >> S;
    deque<char> st; 
    for (auto i=0; i<S.size(); ++i)
    {
        if (!st.empty() && st.back() == S[i])
            st.pop_back();
        else
        {
            st.push_back(S[i]);
        }
    }
    if (st.empty())
        cout << "Empty String";
    else
    {
        for (auto c : st)
            cout << c;
    }    
}
We've worked on this challenge in these gyms: modena 
comments powered by Disqus