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:
- Start with the first character.
- 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:
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.
Video Explanation:
