Stack

Problem You are given a string s consisting only of characters 'a' and 'b'​​​​. You can delete any number of characters in s to make s balanced. s is balanced if there is no pair of indices (i,j) such that i < j and s[i] = 'b' and s[j]= 'a'. Return the minimum number of deletions needed to make s balanced. Examples Example 1: Input: s = "aababbab" Output: 2 Explanation: You can either: Delete the characters at 0-indexed positions 2 and 6 ("aa{b}abb{a}b" -> "aaabbb"), or Delete the characters at 0-i ndexed positions 3 and 6 ("aab{a}bb{a}b" -> "aabbbb"). ...

Problem Given a stack of N elements, interleave the first half of the stack with the second half reversed using only one other queue. This should be done in-place. Recall that you can only push or pop from a stack, and enqueue or dequeue from a queue. Hint: Try working backwards from the end state. Examples Example 1: Input: stack = [1, 2, 3, 4, 5] Output: [1,5,2,4,3] Explanation: We interleave first and last element first - 1, 5, then we interleave 2nd and 2nd last element, 2, 4 and then finally middle element 3. ...

Problem You are given a string s and two integers x and y. You can perform two types of operations any number of times. Remove substring "ab" and gain x points. For example, when removing "ab" from "cabxbae" it becomes "cxbae". Remove substring "ba" and gain y points. For example, when removing "ba" from "cabxbae" it becomes "cabxe". Return the maximum points you can gain after applying the above operations on s. ...

Problem You are given an array representing the heights of neighboring buildings on a city street, from east to west. The city assessor would like you to write an algorithm that returns how many of these buildings have a view of the setting sun, in order to properly value the street. Assumption: Good to clarify with the interviewer, if the heights are equal? For this problem, equal height building don’t obstruct the view, and should be included in answer. ...

Problem Given a string and a set of delimiters, reverse the words in the string while maintaining the relative order of the delimiters. For example, given “hello/world:here”, return “here/world:hello” Follow-up Does your solution work for the following cases: "hello/world:here/", "hello//world:here" Examples Example 1: Input: s = hello/world:here Output: here/world:hello Solution Method 1 - Using stack to store words and queue for delimiters Code Java class Solution { public String reverseWords(String s) { Stack<String> stack = new Stack<>(); Queue<String> queue = new LinkedList<>(); StringBuilder word = new StringBuilder(); int i = 0; while (i < s.length()) { char c = s.charAt(i); if (Character.isLetterOrDigit(c)) { word.append(c); i++; } else { if (word.length() > 0) { stack.push(word.toString()); } word = new StringBuilder(); // clear word for next word StringBuilder delim = new StringBuilder(); delim.append(c); i++; // tracking continuous delimiter to add to queue while (i < s.length() && !Character.isLetterOrDigit(s.charAt(i))) { delim.append(c); i++; } queue.add(delim.toString()); } } // if string ends with words if (word.length() != 0) { stack.push(word.toString()); } boolean isWordFirst = Character.isLetterOrDigit(s.charAt(0)); StringBuilder sb = new StringBuilder(); // if word is not first, add 1 entry from queue if (!isWordFirst) { if (!queue.isEmpty()) { sb.append(queue.remove()); } } // now put 1 element from either till not empty while (!stack.isEmpty() || !queue.isEmpty()) { if (!stack.isEmpty()) { sb.append(stack.pop()); } if (!queue.isEmpty()) { sb.append(queue.remove()); } } return sb.toString(); } } ...

Problem Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram. Examples Example 1: Input: heights = [2,1,5,6,2,3] Output: 10 Explanation: The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units. ...

Problem 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. Examples Example 1: 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". ...

Problem The Leetcode file system keeps a log each time some user performs a change folder operation. The operations are described below: "../" : Move to the parent folder of the current folder. (If you are already in the main folder, remain in the same folder). "./" : Remain in the same folder. "x/" : Move to the child folder named x (This folder is guaranteed to always exist). You are given a list of strings logs where logs[i] is the operation performed by the user at the ith step. ...

Make The String Great Problem Problem Given a string s of lower and upper case English letters. A good string is a string which doesn’t have two adjacent characters s[i] and s[i + 1] where: 0 <= i <= s.length - 2 s[i] is a lower-case letter and s[i + 1] is the same letter but in upper-case or vice-versa. To make the string good, you can choose two adjacent characters that make the string bad and remove them. You can keep doing this until the string becomes good. ...

Problem Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums. The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn’t exist, return -1 for this number. ...