Session 25: Stack and Queue

Original Session

Date: 02 Jan 2025

Topic: Stack & Queue

Concept: Stack created by using Double Linked List

Programs

1. 20. Valid Parentheses
   1. leetcode here

   public boolean isValid(String s) {
   
           if (s.length() <= 1) {
               return false;
           }
   
           Stack<Character> stack = new Stack();
   
           for(Character ch: s.toCharArray()) {
   
               if (!(ch.equals(')') || ch.equals(']') || ch.equals('}'))) {
                   stack.add(ch);
                   continue;
               }
   
               if (stack.isEmpty()) {
                   return false;
               }
   
               Character popedCh = stack.pop();
               switch(ch) {
                   case ')':
                       if (popedCh.equals('(')) {
                           continue;
                       }
                       return false;
                   case ']':
                       if (popedCh.equals('[')) {
                           continue;
                       }
                       return false;
                   case '}':
                       if (popedCh.equals('{')) {
                           continue;
                       }
                       return false;
               }
           }
               return stack.isEmpty();
       }

2. 921. Minimum Add to Make Parentheses Valid
   1. leetcode here

   public int minAddToMakeValid(String s) {
           
           int open = 0, close = 0;
   
           for (char ch: s.toCharArray()) {
   
               if (ch == '(') {
                   open ++;
                   continue;
               }
   
               if (open > 0) {
                   open --;
                    continue;
               }
               close ++;
           }
   
           return open + close;
       }

3. 32. Longest Valid Parentheses
   1. leetcode here

   public int longestValidParentheses(String s) {
           
           int open = 0, close = 0, ans = 0;
   
           for (char ch: s.toCharArray()) {
   
               if (ch == '(') {
                   open ++;
               } else {
                   close ++;
               }
   
               if (open < close) {
                   open = 0;
                   close = 0;
               }
   
               if (open == close) {
   
                   if (open + close > ans) {
                       ans = open + close;
                   }
               }
           }
   
           open = 0;
           close = 0;
   
           for (int i=s.length()-1; i>=0; i--) {
   
               if (s.charAt(i) == ')') {
                   close ++;
               } else {
                   open ++;
               }
   
               if (open > close) {
                   open = 0;
                   close =0;
               }
   
               if (open == close && (open+close>ans)) {
                   ans = open+close;
               }
           }
           return ans;
       }