Stacks

Introduction 

Stacks

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. It means that the element which is inserted last is the first one to be removed. The two primary operations on a stack are push (inserting an element onto the stack) and pop (removing the top element from the stack).

Now, let's solve a question called "Valid Parentheses" using the stack concept.

Problem: Given a string containing only parentheses - '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

Here's the solution code in Python with proper comments explaining each step:

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, x):
        # Push the element onto the stack
        self.stack.append(x)

    def pop(self):
        # Pop the top element from the stack if it's not empty
        if not self.is_empty():
            return self.stack.pop()

    def peek(self):
        # Return the top element from the stack without removing it
        if not self.is_empty():
            return self.stack[-1]

    def is_empty(self):
        # Check if the stack is empty
        return len(self.stack) == 0

def is_valid_parentheses(s):
    stack = Stack()
    opening = ['(', '{', '[']
    closing = [')', '}', ']']
    
    for char in s:
        if char in opening:
            # Push opening parentheses onto the stack
            stack.push(char)
        elif char in closing:
            # Check if the closing parentheses matches the top element of the stack
            if stack.is_empty() or opening.index(stack.pop()) != closing.index(char):
                return False
    
    # The stack should be empty if all parentheses are matched correctly
    return stack.is_empty()

In this code, we create a Stack class with three main operations: push, pop, and peek.

The push operation appends the given element to the top of the stack.

The pop operation removes and returns the top element from the stack if it's not empty.

The peek operation returns the top element from the stack without removing it.

The is_empty operation checks if the stack is empty by checking the length of the stack.

In the is_valid_parentheses function, we create an instance of the Stack class and initialize two lists, opening and closing, which contain the opening and closing parentheses respectively.

We iterate through each character in the input string s. If the character is an opening parenthesis, we push it onto the stack. If the character is a closing parenthesis, we check if it matches the top element of the stack. If not, or if the stack is empty, we return False as the parentheses are not valid.

After iterating through all the characters, we check if the stack is empty. If it's empty, it means all the parentheses are matched correctly, and we return True. Otherwise, we return False.

Time and Space Complexity

The time complexity of the push, pop, peek, and is_empty operations in the stack implementation is O(1) since they involve simple operations on the stack list.

For the is_valid_parentheses function, the time complexity is O(n), where n is the length of the input string s. We iterate through each character in s, and the operations performed in each iteration take constant time.

The space complexity of the implementation is O(n) in the worst case, where n is the length of the input string s. This is because the stack can hold all the opening parentheses in the worst case scenario, where s consists only of opening parentheses.

Let's solve a question that involves using the stack concept. The problem we'll solve is "Remove All Adjacent Duplicates in String".

Problem: Remove All Adjacent Duplicates in String

Given a string S, remove all adjacent duplicates from the string repeatedly until no adjacent duplicates are left. Return the final string after all such duplicate removals.

Example: Input: S = "abbaca" Output: "ca" Explanation: Step 1: Remove "bb" from "abbaca" to get "aaca". Step 2: Remove "aa" from "aaca" to get "ca".

Here's the Python code to solve the problem:

def removeDuplicates(S):
    stack = []
    
    for char in S:
        if stack and stack[-1] == char:
            stack.pop()
        else:
            stack.append(char)
    
    return "".join(stack)
    
# Test the removeDuplicates function
S = "abbaca"
print("Input:", S)
print("Output:", removeDuplicates(S))

In this solution, we use a stack to keep track of the characters. We iterate through each character in the input string. If the stack is not empty and the current character is the same as the top of the stack, we remove the top character from the stack (as it forms an adjacent duplicate pair). Otherwise, we push the current character onto the stack. After iterating through all characters, we join the remaining characters in the stack to form the final string.

The time complexity of this solution is O(n), where n is the length of the input string. We iterate through each character in the string once. The space complexity is also O(n) in the worst case, as the stack may hold all the characters in the string if there are no adjacent duplicates.

Let's solve another LeetCode question that involves using the stack concept. The problem we'll solve is "Valid Parentheses" (LeetCode #20).

Problem: Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Example 1: Input: s = "()" Output: True

Example 2: Input: s = "()[]{}" Output: True

Example 3: Input: s = "(]" Output: False

Here's the Python code to solve the problem:

def isValid(s):
    stack = []
    opening_brackets = "({["
    closing_brackets = ")}]"
    
    for char in s:
        if char in opening_brackets:
            stack.append(char)
        elif char in closing_brackets:
            if not stack:
                return False
            opening_bracket = stack.pop()
            if opening_brackets.index(opening_bracket) != closing_brackets.index(char):
                return False
    
    return len(stack) == 0
    
# Test the isValid function
s = "()[]{}"
print("Input:", s)
print("Output:", isValid(s))

In this solution, we use a stack to keep track of the opening brackets encountered. We iterate through each character in the input string. If the character is an opening bracket, we push it onto the stack. If the character is a closing bracket, we check if the stack is empty (indicating a mismatch) or if the opening bracket at the top of the stack does not correspond to the closing bracket. If any of these conditions are met, the string is not valid, and we return False. At the end, we check if the stack is empty to ensure all opening brackets have been closed.

The time complexity of this solution is O(n), where n is the length of the input string. We iterate through each character in the string once. The space complexity is also O(n) in the worst case, as the stack may hold all the opening brackets if there are no closing brackets or if the string is entirely composed of opening brackets.