LeetCode: Minimum Deletion Cost To Avoid Repeating Letters Solution

Approach

Update the latest local max to calculate the right min

Implementation

1function Stack() {
2  const stack = []
3
4  this.push = function (el) {
5    stack.push(el)
6  }
7
8  this.pop = function () {
9    return stack.pop()
10  }
11
12  this.peek = function () {
13    return stack[stack.length - 1]
14  }
15
16  this.isEmpty = function () {
17    return stack.length === 0
18  }
19}
20
21/**
22 * @param {string} s
23 * @param {number[]} cost
24 * @return {number}
25 */
26var minCost = function (s, cost) {
27  let res = 0,
28    prev = 0
29  for (let i = 1; i < s.length; i++) {
30    if (s[i] === s[i - 1]) {
31      res += Math.min(cost[prev], cost[i])
32      if (cost[i] > cost[prev]) {
33        prev = i
34      }
35    } else {
36      prev = i
37    }
38  }
39  return res
40}
41
42var minCost = function (s, cost) {
43  const stack = new Stack()
44  let res = 0
45  for (let i = 0; i < s.length; i++) {
46    if (s[stack.peek()] !== s[i]) {
47      stack.push(i)
48      continue
49    }
50
51    res += Math.min(cost[stack.peek()], cost[i])
52    if (cost[i] > cost[stack.peek()]) {
53      stack.pop()
54      stack.push(i)
55    }
56  }
57  return res
58}