Home Strings [Hackerrank] – Super Reduced Strings

# [Hackerrank] – Super Reduced Strings

Let us try to understand this problem statement first. We have some strings that needs to be super reduced in size. The string consists of english alphabets from a to z, and they can be duplicated at some places. If we see two adjacent characters that are same, they can be eliminated. Following this pattern we have to return a super compressed/reduced string.

Let us look at some sample test cases:

Input: aabcccdd
Output: “bc”
Explanation:
aabcccdd -> bcccdd -> bcdd -> bc
(we eliminate two same adjacent characters at each step)

Input: abba
Output: “”
Explanation:
abba -> aa -> ” “
The string eventually becomes empty after getting super reduced

#### Method 1:

A brute force solution to the problem is very straight forward. You start to analyze the string from the beginning, and as soon as you see a matching adjacent character, remove both the characters. Start again from the start position and keep on repeating the process.

You will eventually land up with super reduced strings. But the main problem with this approach is that you will waste a lot of time going over the string again and again. We need to find a time efficient way to solve it.

#### Method 2:

Whenever we want to look back at the previous elements, a stack data structure is a very wise choice.

One approach to solve the problem could be:

• Check the top of stack. If it is same, then pop the stack.
• If the top character is different/empty, just push the current character into the stack.

Eventually, when this process runs for the entire string, all the adjacent characters will get removed. You will be left with a reduced string with characters that could not find a matching adjacent character.

#### Code:

.wp-block-code {
border: 0;
}

.wp-block-code > span {
display: block;
overflow: auto;
}

.shcb-language {
border: 0;
clip: rect(1px, 1px, 1px, 1px);
-webkit-clip-path: inset(50%);
clip-path: inset(50%);
height: 1px;
margin: -1px;
overflow: hidden;
position: absolute;
width: 1px;
word-wrap: normal;
word-break: normal;
}

.hljs {
box-sizing: border-box;
}

.hljs.shcb-code-table {
display: table;
width: 100%;
}

.hljs.shcb-code-table > .shcb-loc {
color: inherit;
display: table-row;
width: 100%;
}

.hljs.shcb-code-table .shcb-loc > span {
display: table-cell;
}

.wp-block-code code.hljs:not(.shcb-wrap-lines) {
white-space: pre;
}

.wp-block-code code.hljs.shcb-wrap-lines {
white-space: pre-wrap;
}

.hljs.shcb-line-numbers {
border-spacing: 0;
counter-reset: line;
}

.hljs.shcb-line-numbers > .shcb-loc {
counter-increment: line;
}

.hljs.shcb-line-numbers .shcb-loc > span {
}

.hljs.shcb-line-numbers .shcb-loc::before {
border-right: 1px solid #ddd;
content: counter(line);
display: table-cell;
text-align: right;
-webkit-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
white-space: nowrap;
width: 1%;
}
  public String superReducedStringUsingStacks(String str) {

Stack<Character> characterStack = new Stack<>();

for (int i = 0; i < str.length(); i++) {
char x = str.charAt(i);

if (characterStack.isEmpty())
characterStack.push(x);
else if (x == characterStack.peek())
characterStack.pop();
else
characterStack.push(x);
}

StringBuilder resultBuilder = new StringBuilder();
for (Character character : characterStack)
resultBuilder.append(character);

return resultBuilder.length() == 0 ?
"Empty String" : resultBuilder.toString();
}
Code language: Java (java)

Time Complexity: O(n)
Space Complexity: O(n)

You can also find the code and test cases on Github.

#### You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More