Min stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.
Hold an array/pair in the stack: <currentElement, minSoFarInclusive> and perform the operations
Stack<int[]> stack;
public MinStack() {
stack = new Stack<>();
}
public void push(int val) {
if (stack.isEmpty()) {
stack.push(new int[]{val, val});
} else {
stack.push(new int[]{val, val < stack.peek()[1] ? val : stack.peek()[1]});
}
}
public void pop() {
stack.pop();
}
public int top() {
return stack.peek()[0];
}
public int getMin() {
return stack.peek()[1];
}Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
Push open brackets into stack and pop if corresponding closed one appears. If top of stack does not correspond, or stack in not empty at the end, it is invalid.
Map<Character, Character> map = new HashMap<>();
map.put(‘}’, ‘{‘);
map.put(‘]’, ‘[’);
map.put(‘)’, ‘(‘);
Stack<Character> stack = new Stack();
for(int i=0; i<s.length(); i++) {
char c = s.charAt(i);
if (c=='[' || c=='{' || c=='(')
stack.push(c);
else {
if (stack.isEmpty() || stack.peek()!=map.get(c)) return false;
stack.pop();
}
}
return stack.isEmpty();</Character>
Decode String
Given an encoded string, return its decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].
The test cases are generated so that the length of the output will never exceed 105.
Example 1:
Input: s = “3[a]2[bc]”
Output: “aaabcbc”
Example 2:
Input: s = “3[a2[c]]”
Output: “accaccacc”
Use stack to store the nested structure, and store the current string, as well as current number.
Stack<String> stack = new Stack<>();
StringBuilder currentString = new StringBuilder();
int currentNumber = 0;
for(char c: s.toCharArray()) {
if (Character.isLetter(c)) {
currentString.append(c);
} else if (Character.isDigit(c)) {
currentNumber = currentNumber*10+(c-'0');
} else if (c=='[') {
stack.push(currentString.toString());
stack.push(String.valueOf(currentNumber));
currentString = new StringBuilder();
currentNumber = 0;
} else {
int number = Integer.parseInt(stack.pop());
String previousString = stack.pop();
StringBuilder newCurrentString = new StringBuilder();
newCurrentString.append(previousString);
for(int i=1; i<=number; i++) {
newCurrentString.append(currentString.toString());
}
currentString = newCurrentString;
}
}
return currentString.toString();Remove All Adjacent Duplicates In String
You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.
We repeatedly make duplicate removals on s until we no longer can.
Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.
Input: s = “abbaca”
Output: “ca”
Explanation:
For example, in “abbaca” we could remove “bb” since the letters are adjacent and equal, and this is the only possible move. The result of this move is that the string is “aaca”, of which only “aa” is possible, so the final string is “ca”.
Use a stack and check if current character is same as the top of the stack. If yes, don’t include it in the output
Using a deque to make it easy to poll items in order:
if (s == null || s.length() == 0) return "";
Deque<Character> deque = new LinkedList<>();
for(int index=0; index < s.length(); index++) {
if (deque.isEmpty() || deque.peekLast() != s.charAt(index)) {
deque.add(s.charAt(index));
} else {
while(!deque.isEmpty() && deque.peekLast() == s.charAt(index)) {
deque.pollLast();
}
}
}
StringBuilder result = new StringBuilder();
while(!deque.isEmpty()) {
result.append(deque.pollFirst());
}
return result.toString();O(N) time, for string of length N, space is O(N-D) where D is total number of such duplicates
Remove All Adjacent Duplicates in String II
You are given a string s and an integer k, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them, causing the left and the right side of the deleted substring to concatenate together.
We repeatedly make k duplicate removals on s until we no longer can.
Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique.
Input: s = “deeedbbcccbdaa”, k = 3
Output: “aa”
Explanation:
First delete “eee” and “ccc”, get “ddbbbdaa”
Then delete “bbb”, get “dddaa”
Finally delete “ddd”, get “aa”
Same approach, store characters in stack/deque and poll when we have same character k-1 consecutive times at the top. So save in stack/deque: Pair<character, number of consecutive times it is here in final output, indexed by 1>
if (s == null || s.length() ==0) return "";
Deque<Pair<Character, Integer>> deque = new LinkedList<>();
for(int index=0; index < s.length(); index++) {
if (deque.isEmpty() || deque.peekLast().getKey()!=s.charAt(index)) {
deque.addLast(new Pair<>(s.charAt(index), 1));
} else {
if (deque.peekLast().getValue() == k-1) {
for(int i=0; i < k-1; i++)
deque.pollLast();
} else {
deque.addLast(new Pair<>(s.charAt(index), deque.peekLast().getValue()+1));
}
}
}
StringBuilder sb = new StringBuilder();
while(!deque.isEmpty())
sb.append(deque.pollFirst().getKey());
return sb.toString();Longest Valid Parentheses
Given a string containing just the characters ‘(‘ and ‘)’, return the length of the longest valid (well-formed) parentheses substring.
Input: s = “)()())”
Output: 4
Explanation: The longest valid parentheses substring is “()()”.
Push the index of ( onto then stack.
When we encounter a ):
1. it completes a currently to be validated paranthesis string like ()
2. it validates what comes before an already validated substring like (()
When we have an unmatched ), push it’s index to act as the boundary.
int result=0;
Stack<Integer> stack = new Stack<>();
stack.push(-1);
for(int index=0; index<s.length(); index++) {
if (s.charAt(index) == '(') {
stack.push(index);
} else {
stack.pop();
if (!stack.isEmpty()) {
result = Math.max(result, index - stack.peek());
} else {
stack.push(index); //act as the new boundary
}
}
}
return result;
