Stacks&Queues.js

/*
Valid Parentheses

s = "({})"
o/p: true

s = "(){}[]"
o/p: true

s = "(]"
o/p: false

- loop the string & grab each char
- initalize a hash map with parentheses
- if its opening, load them in the stack
- else if its closing, pop from the stack 
- check if the key exists in the hashmap against looped char
- at the end of the loop return true
- when stack is empty
Time & Space complexity O(n)

*/

const validParentheses = (str) => {
  let holder = []
  const matching = {
      "(": ")",
      "[": "]",
      "{": "}"
  }
  for (const s of str) {
    if(s in matching) {
      holder.push(s)
    }
    else {
      if (matching[holder.pop()] != s) {
        return false
      }
  }
  return holder.length === 0
}}
  
/*
Remove All Adjacent Duplicates In String

i/p: s = "abbaca", 
First remove the "bb" to get "aaca". 
Next, remove the "aa" to get "ca"
o/p: "ca"

- in a loop grab each char, 
- if stack empty then load a char or preload a char
- check if the top char is similar to peek (stack[stack.length - 1])
- then don't add them to stack & pop the char
- if different add them to stack
Time & Space complexity O(n)

*/

const removeDuplicates = (str) => {
  let holder = []
  for (const s of str) {
    if(holder.length === 0 || (holder[holder.length - 1]) != s) {
      holder.push(s);
    }
    else {
      holder.pop();
    }
  }
  console.log('s', holder.join(""))
  return holder.join("");
  
}

removeDuplicates('abbaca')

/*
Backspace String Compare
- If they are equal when both are typed into empty text editors. '#' means a backspace character.
s = "ab#c" and t = "ad#c"
return true. Because of the backspace, the strings are both equal to "ac".

- need to compare 2 strings
- use closure & create a function
- load each char & push them into stack, 
- if # pop a char from the stack
- then compare & return the response
Time & Space complexity O(n)

*/

const backspaceCompare = (r, t) => {
  let build = s => {
    let stack = []
    for (const str of s) {
      if(str != '#') {
        stack.push(str);
      }
      else {
        stack.pop()
      }
    }
    return stack.join("");
  }
  return build(r) === build(t)
}

/*
Simplify Path:
Change path to canonical path
i/p: /a/b//c/.././d/..f/
o/p: /a/b/f

- loop the string & grab each char follow these steps
- push char into stack
- /, //, ., ignore
- .. pop char
- at the end of loop join the string with /

Time & Space Analysis ; O(N)

*/

const simplifyPath = (path) => {
  let stack = [];
  const dirs = path.split("/");
  console.log('dirs', dirs)
  for (const dir of dirs) {
    if(dir === '..' && stack.length === 0 ) {
      stack.push(dir)
    }
    if(dir === '..' && stack.length !== 0 ) {
      stack.pop()
    }
    else if (dir != '' && dir != '.') {
      stack.push(dir)
    }
  }
  console.log('stck', '/' +stack.join('/'))
  return '/' + stack.join('/')
};

simplifyPath("/../")

/*
Make the string great again
- loop each char
- use peek
- pop from stack if peek & char are unequal && char.tolower & peek.toLower
- else push them on to stack
- end of the loop, join the string & return
*/
const makeGood = (str) => {
  let stack = [];
  for (const s of str) {
    const peek = stack[stack.length - 1];
    if(stack.length > 0 && peek !== s && s.toLowerCase() === peek.toLowerCase()) {
      stack.pop();
    }
    else {
      stack.push(s);
    }
  }
  console.log('str', stack.join(''))
  return stack.join('')
};

makeGood("leEeetcode") 

// Queue

let queue = [];

let queue = [1,2,3];

// Enqueueing/adding elements
queue.push(4);
queue.push(5);

// Dequeuing/removing elements
queue.shift(); // 1
queue.shift(); // 1

// Check element at front of queue (next element to be removed)
queue[0]; // 3

// get size
queue.length; // 3

RecentCounter.prototype.ping = function(t) {
  while (this.queue.length && this.queue[0] < t - 3000) {
    this.queue.shift();
  }
  this.queue.push(t);
  return this.queue.length

}