Home

647. Palindromic Substrings Solutions Solution 1: For each char in the string, there are 2 kinds of palindromic substring possible: odd substring even substring Expand from each char as a center for both odd and even substring. Solution 2: Manacher’s Algorithm Reference def countSubstrings(self, s): """ :type s...

19. Remove Nth Node From End of List Solutions Loop twice Loop through the list to count the length of this list Loop through the list again until meets the (length - n)th node from the beginning Loop once Keep two pointer slow and fast, where fast is n+1 step faster than slow. When fast reaches to the end, slow is pointing to the corr...

200. Number of Islands Solutions Each 1-tile should mark any 1-neighbours of it The idea is similar to painting game for child.

76. Minimum Window Substring Solutions Create a filtered_S that contains all characters and their index that should appear in target string Apply sliding window algorithm to filtered_S Time Complexity: $O(\mid S \mid + \mid T \mid)$ Space Complexity: $O(\mid S \mid + \mid T \mid)$

424. Longest Repeating Character Replacement Solutions Sliding Window with tolerance Keep pointer start and curr, a dictionary of num_occurance and max_occurance If curr - start + 1 - max_occurance > tolerance Move start to next Update num_occurance num_occurance[ord(s[start]) - ord('A')] -= 1 No nee...

3. Longest Substring Without Repeating Characters Solutions Sliding Window Keep pointer start and curr, a set of occurred characters If s[curr] has occurred, move start to next and update occurred until s[curr] is not inside occurred Keep the largest curr - start + 1 as the result

153. Find Minimum in Rotated Sorted Array Solutions Binary Search Use start, end, mid to decide whether left and right side is rotated

11. Container With Most Water Solutions Sliding Window - Shrink Shrink the window by always moving the lower side