Han Zhu's Study Notes

Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters. Example 1: Input: "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c". Example 2: Input: "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa". Note: The input string length won't exceed 1000. Thought process: Dynamic programming. Use a matrix to check if s[i,j] is a palindrome. If so, add one to count. Sub-problem: check if a sub-string of s is a palindrome. Function:  If s[i] == s[j]: If j - i < 2 (one character or two characters), f[i][j] = true. Otherwise, f[i][j] = f[i + 1][j - 1]. Otherwise, f[i][j] = false. Initialization: none. Answer: f[0][n - 1] will sa...

Your are given an array of integers  prices , for which the  i -th element is the price of a given stock on day  i ; and a non-negative integer  fee  representing a transaction fee. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.) Return the maximum profit you can make. Example 1: Input: prices = [1, 3, 2, 8, 4, 9], fee = 2 Output: 8 Explanation: The maximum profit can be achieved by: Buying at prices[0] = 1 Selling at prices[3] = 8 Buying at prices[4] = 4 Selling at prices[5] = 9 The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8. Note: 0 < prices.length <= 50000 . 0 < prices[i] < 50000 . 0 <= fee < 50000 . Thought process: Each day there are two options, buy or sell. Use two variables buy and sell to keep track of the max profit. Solutio...

In a given array  nums  of positive integers, find three non-overlapping subarrays with maximum sum. Each subarray will be of size  k , and we want to maximize the sum of all  3*k  entries. Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one. Example: Input: [1,2,1,2,6,7,5,1], 2 Output: [0, 3, 5] Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5]. We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger. Note: nums.length  will be between 1 and 20000. nums[i]  will be between 1 and 65535. k  will be between 1 and floor(nums.length / 3). Thought process: Dynamic programming. Create an array of sums of windows of size k. This array's length will be nums.length - k + 1, because an array can have this many choices of windows. I...

The demons had captured the princess ( P ) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight ( K ) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess. The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately. Some of the rooms are guarded by demons, so the knight loses health ( negative  integers) upon entering these rooms; other rooms are either empty ( 0's ) or contain magic orbs that increase the knight's health ( positive  integers). In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step. Write a function to determine the knight's minimum initial health so that he is able to rescue the princess. For example, given the dungeon below, the initial health of th...

Given a 2D grid, each cell is either a wall  'W' , an enemy  'E'  or empty  '0'  (the number zero), return the maximum enemies you can kill using one bomb. The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since the wall is too strong to be destroyed. Note that you can only put the bomb at an empty cell. Example: For the given grid 0 E 0 0 E 0 W E 0 E 0 0 return 3. (Placing a bomb at (1,1) kills 3 enemies) Thought process: Iterate through the matrix. Use global variables to keep track of row hits and column hits. These will propagate until we reach a wall. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution { public int maxKilledEnemies ( char [][] grid ) { int height = grid . length ; if ( height == 0 ) { return 0 ; } int width = grid [ 0 ]. length ;...

Given a  rows x cols  screen and a sentence represented by a list of  non-empty  words, find  how many times  the given sentence can be fitted on the screen. Note: A word cannot be split into two lines. The order of words in the sentence must remain unchanged. Two consecutive words  in a line  must be separated by a single space. Total words in the sentence won't exceed 100. Length of each word is greater than 0 and won't exceed 10. 1 ≤ rows, cols ≤ 20,000. Example 1: Input: rows = 2, cols = 8, sentence = ["hello", "world"] Output: 1 Explanation: hello--- world--- The character '-' signifies an empty space on the screen. Example 2: Input: rows = 3, cols = 6, sentence = ["a", "bcd", "e"] Output: 2 Explanation: a-bcd- e-a--- bcd-e- The character '-' signifies an empty space on the screen. Example 3: Input: rows = 4, cols = 5, sentence = ["I", "had", ...

Given a 2D matrix  matrix , find the sum of the elements inside the rectangle defined by its upper left corner ( row 1,  col 1) and lower right corner ( row 2,  col 2). The above rectangle (with the red border) is defined by (row1, col1) =  (2, 1)  and (row2, col2) =  (4, 3) , which contains sum =  8 . Example: Given matrix = [ [3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5] ] sumRegion(2, 1, 4, 3) -> 8 sumRegion(1, 1, 2, 2) -> 11 sumRegion(1, 2, 2, 4) -> 12 Note: You may assume that the matrix does not change. There are many calls to  sumRegion  function. You may assume that  row 1 ≤  row 2 and  col 1 ≤  col 2. Thought process: Get the "prefix sum" of the matrix first. sum[i][j] = matrix[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]. Then use it to calculate sumRegion.  Solution: 1 2 3 4 5 6 7 8 9 10 1...

Given an unsorted array of integers, find the number of longest increasing subsequence. Example 1: Input: [1,3,5,4,7] Output: 2 Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7]. Example 2: Input: [2,2,2,2,2] Output: 5 Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5. Note:  Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int. Thought process: DP.  Sub-problem: find the number and length of the longest increasing subsequence ending at index i. Function: f[i] = max(f[0,...,i] where nums[j] < nums[i]) + 1 or 1 if no nums[0,...,i] is less than nums[i]. counts[i] = sum(counts[0,...i]) where f[j] = max(f[0,...,i]) where nums[j] < nums[i]. Initialization: f[0] = 1. counts[0] = 1. Answer: max(counts) where f[i] == max(f). Solution: 1 2 3 4 5 6 7 8 ...

Given a  non-empty  array containing  only positive integers , find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal. Note: Each of the array element will not exceed 100. The array size will not exceed 200. Example 1: Input: [1, 5, 11, 5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11]. Example 2: Input: [1, 2, 3, 5] Output: false Explanation: The array cannot be partitioned into equal sum subsets. Thought process: DP. Calculate the sum of all numbers. If it's odd, return false. Sub-problem: check if a sub-array can sum to a number between 0 and sum / 2. Function: f[i + num] = true if f[i] == true. Initialization: f = new boolean[sum / 2 + 1]. Fill f[0] with true. Answer: the last element of f. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public boolean canPartition ( int ...