Problem: 1D Candy Crush: You are given a string. You have to eliminate all occurrences of 3 or more adjacent identical characters in a string. For Example: if you are given "aaabbbbbacddddd", then the output must be "ac".
I solved the problem using a stack. The Initial solution was failing a few test cases. However, the interviewer guided me and gave me hints. I got to the solution eventually.
Below is the code.
import java.util.Stack;
public class CandyCrush1D {
private static class Wrapper
{
private char c;
int count;
private Wrapper(char c, int count) {
this.c = c;
this.count = count;
}
}
public static void main(String[] args) {
String s = "aaabbbbbacddddd";
System.out.println(remove3ConsecutiveChars(s));
}
private static String remove3ConsecutiveChars(String s)
{
Stack<Wrapper> stack = new Stack<>();
StringBuilder ans = new StringBuilder();
for(int i = 0; i < s.length(); i++)
{
if (stack.isEmpty() || s.charAt(i) != stack.peek().c) {
if (!stack.isEmpty() && stack.peek().count > 2)
stack.pop();
stack.push(new Wrapper(s.charAt(i), 1));
}
else
{
Wrapper wrapper = stack.pop();
stack.push(new Wrapper(s.charAt(i), wrapper.count + 1));
}
}
if (!stack.isEmpty() && stack.peek().count > 2)
stack.pop();
while (!stack.isEmpty())
ans.append(stack.pop().c);
return ans.reverse().toString();
}
}I have no idea what went wrong. I was expecting the onsite call this week.
Comments (6)