Super Reduced String HackerRank Solution

Super Reduced String HackerRank Solution
Source : https://www.hackerrank.com/challenges/reduced-string

Steve has a string of lowercase characters in range ascii[‘a’..’z’]. He wants to reduce the string to its shortest length by doing a series of operations. In each operation he selects a pair of adjacent lowercase letters that match, and he deletes them. For instance, the string aab could be shortened to b in one operation.

Steve’s task is to delete as many characters as possible using this method and print the resulting string. If the final string is empty, print Empty String

Function Description

Complete the superReducedString function in the editor below. It should return the super reduced string or Empty String if the final string is empty.

superReducedString has the following parameter(s):

• s: a string to reduce

Input Format

A single string, .

Constraints

Output Format

If the final string is empty, print Empty String; otherwise, print the final non-reducible string.

Sample Input 0

aaabccddd

Sample Output 0

abd

Explanation 0

Steve performs the following sequence of operations to get the final string:

aaabccddd → abccddd → abddd → abd

Sample Input 1

aa

Sample Output 1

Empty String

Explanation 1

aa → Empty String

Sample Input 2

baab

Sample Output 2

Empty String

Explanation 2

baab → bb → Empty String

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

Solution

	// Karthikalapati.blogspot.com
	import java.util.Scanner;
	import java.util.Stack;
	// Time Complexity: O(n)
	// Space Complexity: O(n)
	// Can alternatively use an ArrayDeque instead of a Stack. Just make sure to iterate
	// through it properly since iteration order is opposite that of a Stack.
	String superReducedString(String str) {
	/* Iterate through String, creating final result in a Stack */
	Stack<Character> stack = new Stack();
	for (int i = 0; i < str.length(); i++) {
	Character ch = str.charAt(i);
	if (!stack.isEmpty() && ch == stack.peek()) {
	stack.pop(); // since String has 2 adjacent equal characters
	} else {
	stack.push(ch);
	}
	}
	/* Return final result */
	if (stack.isEmpty()) {
	return "Empty String";
	} else {
	StringBuffer sb = new StringBuffer();
	for (char ch : stack) {
	sb.append(ch);
	}
	return sb.toString();
	}
	}
	// Discuss on HackerRank: https://www.hackerrank.com/challenges/reduced-string/forum/comments/263979