Han Zhu's Study Notes

Given a string, find the length of the  longest substring  without repeating characters. Examples: Given  "abcabcbb" , the answer is  "abc" , which the length is 3. Given  "bbbbb" , the answer is  "b" , with the length of 1. Given  "pwwkew" , the answer is  "wke" , with the length of 3. Note that the answer must be a  substring ,  "pwke"  is a  subsequence  and not a substring. Thought process: Two pointers + sliding window: Pointer i points to the left end of current window. Pointer j points to the right end of current window. Use a hash set to keep track of the characters in current window. Iterate through the string using j. If s[j] is a repeating character, increment i and remove s[i] from set until no repeating character is there. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int lengthOfLongestSubstring ( String s ) { ...

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...