# Posts tagged as “stack”

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.

Return the string after making it good. The answer is guaranteed to be unique under the given constraints.

Notice that an empty string is also good.

Example 1:

Input: s = "leEeetcode"
Output: "leetcode"
Explanation: In the first step, either you choose i = 1 or i = 2, both will result "leEeetcode" to be reduced to "leetcode".


Example 2:

Input: s = "abBAcC"
Output: ""
Explanation: We have many possible scenarios, and all lead to the same answer. For example:
"abBAcC" --> "aAcC" --> "cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""


Example 3:

Input: s = "s"
Output: "s"


Constraints:

• 1 <= s.length <= 100
• s contains only lower and upper case English letters.

## Solution: Stack

Iterator over the string, compare current char with top of the stack, if they are a bad pair, pop the stack (remove both of them). Otherwise, push the current char onto the stack.

input: “abBAcC”
“a”
“ab”
“abB” -> “a”
aA” -> “”
“c”
cC” -> “”
ans = “”

Time complexity: O(n)
Space complexity: O(n)

## Python3

Given a rows * columns matrix mat of ones and zeros, return how many submatrices have all ones.

Example 1:

Input: mat = [[1,0,1],
[1,1,0],
[1,1,0]]
Output: 13
Explanation:
There are 6 rectangles of side 1x1.
There are 2 rectangles of side 1x2.
There are 3 rectangles of side 2x1.
There is 1 rectangle of side 2x2.
There is 1 rectangle of side 3x1.
Total number of rectangles = 6 + 2 + 3 + 1 + 1 = 13.


Example 2:

Input: mat = [[0,1,1,0],
[0,1,1,1],
[1,1,1,0]]
Output: 24
Explanation:
There are 8 rectangles of side 1x1.
There are 5 rectangles of side 1x2.
There are 2 rectangles of side 1x3.
There are 4 rectangles of side 2x1.
There are 2 rectangles of side 2x2.
There are 2 rectangles of side 3x1.
There is 1 rectangle of side 3x2.
Total number of rectangles = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24.


Example 3:

Input: mat = [[1,1,1,1,1,1]]
Output: 21


Example 4:

Input: mat = [[1,0,1],[0,1,0],[1,0,1]]
Output: 5


Constraints:

• 1 <= rows <= 150
• 1 <= columns <= 150
• 0 <= mat[i][j] <= 1

## Solution 1: Brute Force w/ Pruning

Time complexity: O(m^2*n^2)
Space complexity: O(1)

## C++

Given an array target and an integer n. In each iteration, you will read a number from  list = {1,2,3..., n}.

Build the target array using the following operations:

• Push: Read a new element from the beginning list, and push it in the array.
• Pop: delete the last element of the array.
• If the target array is already built, stop reading more elements.

You are guaranteed that the target array is strictly increasing, only containing numbers between 1 to n inclusive.

Return the operations to build the target array.

You are guaranteed that the answer is unique.

Example 1:

Input: target = [1,3], n = 3
Output: ["Push","Push","Pop","Push"]
Explanation:
Read number 1 and automatically push in the array -> [1]
Read number 2 and automatically push in the array then Pop it -> [1]
Read number 3 and automatically push in the array -> [1,3]


Example 2:

Input: target = [1,2,3], n = 3
Output: ["Push","Push","Push"]


Example 3:

Input: target = [1,2], n = 4
Output: ["Push","Push"]
Explanation: You only need to read the first 2 numbers and stop.


Example 4:

Input: target = [2,3,4], n = 4
Output: ["Push","Pop","Push","Push","Push"]


Constraints:

• 1 <= target.length <= 100
• 1 <= target[i] <= 100
• 1 <= n <= 100
• target is strictly increasing.

## Solution: Simulation

For each number in target, keep discarding i if i != num by “Push” + “Pop”, until i == num. One more “Push”.

Time complexity: O(n)
Space complexity: O(n) or O(1) w/o output.

## C++

Given the string croakOfFrogs, which represents a combination of the string “croak” from different frogs, that is, multiple frogs can croak at the same time, so multiple “croak” are mixed. Return the minimum number of different frogs to finish all the croak in the given string.

A valid “croak” means a frog is printing 5 letters ‘c’, ’r’, ’o’, ’a’, ’k’ sequentially. The frogs have to print all five letters to finish a croak. If the given string is not a combination of valid “croak” return -1.

Example 1:

Input: croakOfFrogs = "croakcroak"
Output: 1
Explanation: One frog yelling "croak" twice.


Example 2:

Input: croakOfFrogs = "crcoakroak"
Output: 2
Explanation: The minimum number of frogs is two.
The first frog could yell "crcoakroak".
The second frog could yell later "crcoakroak".


Example 3:

Input: croakOfFrogs = "croakcrook"
Output: -1
Explanation: The given string is an invalid combination of "croak" from different frogs.


Example 4:

Input: croakOfFrogs = "croakcroa"
Output: -1


Constraints:

• 1 <= croakOfFrogs.length <= 10^5
• All characters in the string are: 'c''r''o''a' or 'k'.

## Solution: Hashtable

Count the frequency of the letters, we need to make sure f[c] >= f[r] >= f[o] >= f[a] >= f[k] holds all the time, otherwise return -1.
whenever encounter c, increase the current frog, whenever there is k, decrease the frog count.
Don’t forget to check the current frog number, should be 0 in the end, otherwise there are open letters.

Time complexity: O(n)
Space complexity: O(1)

## C++

Given alphanumeric string s. (Alphanumeric string is a string consisting of lowercase English letters and digits).

You have to find a permutation of the string where no letter is followed by another letter and no digit is followed by another digit. That is, no two adjacent characters have the same type.

Return the reformatted string or return an empty string if it is impossible to reformat the string.

Example 1:

Input: s = "a0b1c2"
Output: "0a1b2c"
Explanation: No two adjacent characters have the same type in "0a1b2c". "a0b1c2", "0a1b2c", "0c2a1b" are also valid permutations.


Example 2:

Input: s = "leetcode"
Output: ""
Explanation: "leetcode" has only characters so we cannot separate them by digits.


Example 3:

Input: s = "1229857369"
Output: ""
Explanation: "1229857369" has only digits so we cannot separate them by characters.


Example 4:

Input: s = "covid2019"
Output: "c2o0v1i9d"


Example 5:

Input: s = "ab123"
Output: "1a2b3"


Constraints:

• 1 <= s.length <= 500
• s consists of only lowercase English letters and/or digits.

## Solution: Two streams

Create two stacks, one for alphas, another for numbers. If the larger stack has more than one element than the other one then no solution, return “”. Otherwise, interleave two stacks, start with the larger one.

Time complexity: O(n)
Space complexity: O(n)

## C++

Mission News Theme by Compete Themes.