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;
    }
}

Haskell, grouping and counting adjacent equal characters, keeping only odd occurrences. The function is recursive and the base case is when original and reduced are equal.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
import Data.List (group)

prettyPrint "" = "Empty String"
prettyPrint s = s

reduce s = if s' == s then s' else reduce s'
  where
    s' = map snd . (filter (odd . fst)) . map (\x -> (length x, head x)) $ group s

main = interact (prettyPrint . reduce)

Same, but with list comprehension:

1
2
3
reduce s = if s' == s then s' else reduce s'
  where
    s' = [v | (n, v) <- (\x -> (length x, head x)) <$> group s, odd n]

Rust, using a stack.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
fn reduce_string(s: String) -> String {
    s.chars().fold(String::new(), |mut acc, c| {
        match acc.pop() {
            None => acc.push(c),
            Some(l) => {
                if l != c {
                    acc.push(l);
                    acc.push(c);
                }
            }
        };

        acc
    })
}
We've worked on this challenge in these gyms: modena  padua  milan 
comments powered by Disqus