# Posts published in “Stack”

Given an absolute path for a file (Unix-style), simplify it. Or in other words, convert it to the canonical path.

In a UNIX-style file system, a period . refers to the current directory. Furthermore, a double period .. moves the directory up a level. For more information, see: Absolute path vs relative path in Linux/Unix

Note that the returned canonical path must always begin with a slash /, and there must be only a single slash / between two directory names. The last directory name (if it exists) must not end with a trailing /. Also, the canonical path must be the shortest string representing the absolute path.

Example 1:

Input: "/home/"
Output: "/home"
Explanation: Note that there is no trailing slash after the last directory name.


Example 2:

Input: "/../"
Output: "/"
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.


Example 3:

Input: "/home//foo/"
Output: "/home/foo"
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.


Example 4:

Input: "/a/./b/../../c/"
Output: "/c"


Example 5:

Input: "/a/../../b/../c//.//"
Output: "/c"


Example 6:

Input: "/a//b////c/d//././/.."
Output: "/a/b/c"

## Solution: Stack

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

## C++

Given a string s, 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.

Example 1:

Input: s = "abcd", k = 2
Output: "abcd"
Explanation: There's nothing to delete.

Example 2:

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"

Example 3:

Input: s = "pbbcggttciiippooaais", k = 2
Output: "ps"


Constraints:

• 1 <= s.length <= 10^5
• 2 <= k <= 10^4
• s only contains lower case English letters.

## Solution: Stack

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

## C++

Given a string s that consists of lower case English letters and brackets.

Reverse the strings in each pair of matching parentheses, starting from the innermost one.

Your result should not contain any bracket.

Example 1:

Input: s = "(abcd)"
Output: "dcba"


Example 2:

Input: s = "(u(love)i)"
Output: "iloveu"


Example 3:

Input: s = "(ed(et(oc))el)"
Output: "leetcode"


Example 4:

Input: s = "a(bcdefghijkl(mno)p)q"
Output: "apmnolkjihgfedcbq"


Constraints:

• 0 <= s.length <= 2000
• s only contains lower case English characters and parentheses.
• It’s guaranteed that all parentheses are balanced.

## Solution: Stack

Use a stack of strings to track all the active strings.
Iterate over the input string:
1. Whenever there is a ‘(‘, push an empty string to the stack.
2. Whenever this is a ‘)’, pop the top string and append the reverse of it to the new stack top.
3. Otherwise, append the letter to the string on top the of stack.

Once done, the (only) string on the top of the stack is the answer.

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

## C++

You have an infinite number of stacks arranged in a row and numbered (left to right) from 0, each of the stacks has the same maximum capacity.

Implement the DinnerPlates class:

• DinnerPlates(int capacity) Initializes the object with the maximum capacity of the stacks.
• void push(int val) pushes the given positive integer val into the leftmost stack with size less than capacity.
• int pop() returns the value at the top of the rightmost non-empty stack and removes it from that stack, and returns -1 if all stacks are empty.
• int popAtStack(int index) returns the value at the top of the stack with the given index and removes it from that stack, and returns -1 if the stack with that given index is empty.

Example:

Input:
["DinnerPlates","push","push","push","push","push","popAtStack","push","push","popAtStack","popAtStack","pop","pop","pop","pop","pop"]
[,,,,,,,,,,,[],[],[],[],[]]
Output:


[null,null,null,null,null,null,2,null,null,20,21,5,4,3,1,-1]

Explanation:
DinnerPlates D = DinnerPlates(2);  // Initialize with capacity = 2
D.push(1);
D.push(2);
D.push(3);
D.push(4);
D.push(5);         // The stacks are now:  2  4
1  3  5
﹈ ﹈ ﹈
D.popAtStack(0);   // Returns 2.  The stacks are now:     4
1  3  5
﹈ ﹈ ﹈
D.push(20);        // The stacks are now: 20  4
1  3  5
﹈ ﹈ ﹈
D.push(21);        // The stacks are now: 20  4 21
1  3  5
﹈ ﹈ ﹈
D.popAtStack(0);   // Returns 20.  The stacks are now:     4 21
1  3  5
﹈ ﹈ ﹈
D.popAtStack(2);   // Returns 21.  The stacks are now:     4
1  3  5
﹈ ﹈ ﹈
D.pop()            // Returns 5.  The stacks are now:      4
1  3
﹈ ﹈
D.pop()            // Returns 4.  The stacks are now:   1  3
﹈ ﹈
D.pop()            // Returns 3.  The stacks are now:   1
﹈
D.pop()            // Returns 1.  There are no stacks.
D.pop()            // Returns -1.  There are still no stacks.



Constraints:

• 1 <= capacity <= 20000
• 1 <= val <= 20000
• 0 <= index <= 100000
• At most 200000 calls will be made to pushpop, and popAtStack.

## Solution: Array of stacks + TreeSet

Store all the stacks in an array, and store the indices of all free stacks in a tree set.
1. push(): find the first free stack and push onto it, if it becomes full, remove it from free set.
2. pop(): pop element from the last stack by calling popAtIndex(stacks.size()-1).
3. popAtIndex(): pop element from given index
3.1 add it to free set if it was full
3.2 remove it from free set if it becomes empty
3.2.1 remove it from stack array if it is the last stack

Time complexity:
Push: O(logn)
Pop: O(logn)
PopAtIndex: O(logn)

Space complexity: O(n)

## C++

Implement the following operations of a queue using stacks.

• push(x) — Push element x to the back of queue.
• pop() — Removes the element from in front of queue.
• peek() — Get the front element.
• empty() — Return whether the queue is empty.

Example:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

Notes:

• You must use only standard operations of a stack — which means only push to toppeek/pop from topsize, and is empty operations are valid.
• Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
• You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

## Solution: Use two stacks

amortized cost: O(1)

## C++

Mission News Theme by Compete Themes.