Notes

// SELECT
// SUM(insurance.TIV_2016) AS TIV_2016
// FROM
// insurance
// WHERE
// insurance.TIV_2015 IN
// (
// SELECT
// TIV_2015
// FROM
// insurance
// GROUP BY TIV_2015
// HAVING COUNT(*) > 1
// )
// AND CONCAT(LAT, LON) IN
// (
// SELECT
// CONCAT(LAT, LON)
// FROM
// insurance
// GROUP BY LAT , LON
// HAVING COUNT(*) = 1
// )
// ;

// select sum(TIV_2016) TIV_2016
// from insurance a
// where 1 = (select count(*) from insurance b where a.LAT=b.LAT and a.LON=b.LON)
// and 1 < (select count(*) from insurance c where a.TIV_2015=c.TIV_2015) ;

// SELECT
// SUM(TIV_2012) AS TIV_2012
// FROM
// Insurance a
// WHERE
// (
// SELECT
// COUNT(*)
// FROM
// Insurance b
// WHERE
// a.LAT = b.lAT
// AND
// a.LON = b.LON
// ) = 1
// AND
// (
// SELECT
// COUNT(*)
// FROM
// Insurance c
// WHERE
// a.TIV_2011 = c.TIV_2011
// ) > 1
// ;

var minMutation = function(start, end, bank) {
if (start === end) return 0;

const dict = {};
bank.forEach(b => dict[b] = true);
const choices = ['A', 'C', 'G', 'T'];

const queue = [start];
const visited = {};
let count = 0;

while (queue.length) {
for (let i = 0, len = queue.length; i < len; i++) {
const cur = queue.shift();
if (cur === end) {
return count;
}
visited[cur] = true;
for (let j = 0; j < cur.length; j++) {
for (let k = 0; k < choices.length; k++) {
const head = cur.slice(0, j);
const tail = cur.slice(j + 1);
const nextStr = head + choices[k] + tail;
if (dict[nextStr] && !visited[nextStr]) {
queue.push(nextStr);
}
}
}
}
count++;
}

return -1;
};

var a = "AACCGGTT";
var b = "AACCGCTA";
var c = ["AACCGGTA","AACCGCTA","AAACGGTA"];
console.log(minMutation(a, b, c));

// class Solution {
// public int minMutation(String start, String end, String[] bank) {
// if (start == end) {
// return 0;
// }

// Set<String> dict = new HashSet<>();
// for (String s : bank) {
// dict.add(s);
// }


// Set<String> visited = new HashSet<>();
// Queue<String> queue = new LinkedList<>();
// queue.offer(start);


// int count = 0;
// char[] choices = new char[] {'A', 'C', 'G', 'T'};

// while (!queue.isEmpty()) {
// for (int i = 0, len = queue.size(); i < len; i++) {
// String cur = queue.poll();
// if (cur.equals(end)) {
// return count;
// }
// visited.add(cur);
// char[] tmp = cur.toCharArray();
// for (int j = 0; j < tmp.length; j++) {
// for (int k = 0; k < choices.length; k++) {
// tmp[j] = choices[k];
// String nextStr = new String(tmp);
// if (dict.contains(nextStr) && !visited.contains(nextStr)) {
// queue.offer(nextStr);
// }

// }
// tmp[j] = cur.charAt(j);
// }
// }
// count++;
// }

// return -1;
// }
// }

var longestValidParentheses = function(s) {
let start = s.indexOf('(');
let end = s.lastIndexOf(')');
let max = 0;

while (start < end) {
for (let i = end; i >= start + max; i--) {
if (isValidParentheses(s, start, i)) {
max = i - start + 1;
}
}
start++;
}

return max;
};

function isValidParentheses(s, left, right) {
if ((right - left) % 2 === 0) {
return false;
}

let leftCount = 0;

while (left <= right) {
if (s[left] === '(') {
leftCount++;
} else if (--leftCount < 0){
return false;
}
left++;
}

return leftCount === 0;
}

var longestValidParentheses = function(s) {
var stack = [-1];
var count = 0;

for (var i=0; i<s.length; i++) {
var top = stack[stack.length-1];

if (s[i] === ')' && s[top] === '(') {
stack.pop(top);
count = Math.max(count, i - stack[stack.length-1]);
} else {
stack.push(i);
}
}

return count;
};

var longestValidParentheses = function(s) {
let start = s.indexOf('(');
let end = s.lastIndexOf(')');

const count = new Uint32Array(s.length);
let max = 0;
let left = 0;
while (start <= end) {
if (s[start] === '(') {
left++;
} else if (s[start] === ')' && left) {
left--;
count[start] += 2 + count[start - 1];
count[start] += count[start - count[start]] || 0;
max = Math.max(max, count[start]);
}
start++;
}

return max;
};

var longestValidParentheses = function(s) {
var stack = [-1];
var count = 0;

for (var i = 0; i < s.length; i++) {
var top = stack[stack.length - 1];

if (s[i] === ')' && s[top] === '(') {
stack.pop(top);
count = Math.max(count, i - stack[stack.length - 1]);
} else {
stack.push(i);
}
}

return count;
};




var a = ')()())';
console.log(longestValidParentheses(a));

var uniquePaths = function(m, n) {
if (n < m) return uniquePaths(n, m);

const paths = new Array(m).fill(1);

for (let i = 1; i < n; i++) {
for (let j = 1; j < m; j++) {
paths[j] += paths[j - 1];
}
}

return paths[m - 1];
};

// class Solution {
// public int uniquePaths(int m, int n) {
// if (n < m) {
// return uniquePaths(n, m);
// }

// int[] dp = new int[m];
// Arrays.fill(dp, 1);

// for (int i = 1; i < n; i++) {
// for (int j = 1; j < m; j++) {
// dp[j] += dp[j - 1];
// }
// }

// return dp[m - 1];
// }
// }

var uniquePaths2 = function(m, n) {
if (n < m) return uniquePaths(n, m);

const paths = new Array(m).fill(1);
const paths2 = new Array(m).fill(1);

for (let i = 1; i < n; i++) {
for (let j = 1; j < m; j++) {
if (i % 2 === 1) {
paths[j] = paths[j - 1] + paths2[j - 1] + paths2[j];
} else {
paths2[j] = paths2[j - 1] + paths[j - 1] + paths[j];
}
}
}

if (n % 2 === 1) {
return paths2[m - 1];
}
return paths[m - 1];
};

console.log(uniquePaths2(3, 3));
console.log(uniquePaths2(4, 4));

var uniquePathsWithObstacles = function(obstacleGrid) {
const row = obstacleGrid.length;
const col = obstacleGrid[0].length;

//if (obstacleGrid[0][0] || obstacleGrid[row - 1][col - 1]) return 0;

const paths = new Array(col).fill(0);

paths[0] = 1;

for (let i = 0; i < row; i++) {
for (let j = 0; j < col; j++) {
if (obstacleGrid[i][j]) {
paths[j] = 0;
} else {
paths[j] += (paths[j - 1] || 0);
}
}
}

return paths[col - 1];
};

var lengthOfLIS = function(nums) {
const dp = new Array(nums.length).fill(1);

for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}

return Math.max(0, ...dp);
};

// SELECT
// d.DEPT_NAME, COUNT(*) AS STUDENT_NUMBER
// FROM
// Student s
// RIGHT JOIN
// DEPARTMENT
// ON
// d.DEPT_ID = s.DEPT_ID
// GROUP BY
// d.DEPT_NAME
// ORDER BY
// STUDENT_NUMBER DESC, d.DEPT_NAME
// ;

// SELECT
// customerNumber
// FROM
// ORDERS
// GROUP BY
// customerNumber
// ORDER BY
// COUNT(orderNumber) DESC
// LIMIT
// 1
// ;