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