LEETCODE SOLUTIONS

647 .  Palindromic Substrings   Given a string  s , return  the number of  palindromic substrings  in it . A string is a  palindrome  when it reads the same backward as forward. A  substring  is a contiguous sequence of characters within the string.   Example 1: Input: s = "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c". Example 2: Input: s = "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".   Constraints: 1 <= s.length <= 1000 s  consists of lowercase English letters. Solution : class Solution: def countSubstrings(self, s: str) -> int: ans = 0 for i in range(len(s)): ans += self.pcount(s, i, i) ans += self.pcount(s, i, i+1) return ans def pcount(self, s, l, r): ans = 0 while l >= 0 and r < len(s) and s[l] == s[r

572 .  Subtree of Another Tree Given the roots of two binary trees  root  and  subRoot , return  true  if there is a subtree of  root  with the same structure and node values of  subRoot  and  false  otherwise. A subtree of a binary tree  tree  is a tree that consists of a node in  tree  and all of this node's descendants. The tree  tree  could also be considered as a subtree of itself.   Example : Input: root = [3,4,5,1,2], subRoot = [4,1,2] Output: true SOLUTION: class Solution: def isSubtree(self, r: Optional[TreeNode], sr: Optional[TreeNode]) -> bool: if not sr: return True if not r: return False if self.sameTree(r,sr): return True return (self.isSubtree(r.left, sr) or self.isSubtree(r.right, sr)) def sameTree(self, r, sr): if not r and not sr: return True if r and sr and r.val == sr.val: return (self.sameTree(r.left, sr.left) and self.same

4 49 .  Serialize and Deserialize BST Serialization is converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize a  binary search tree . There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure. The encoded string should be as compact as possible.   Example 1: Input: root = [2,1,3] Output: [2,1,3] Example 2: Input: root = [] Output: []   Constraints: The number of nodes in the tree is in the range  [0, 10 4 ] . 0 <= Node.val <= 10 4 The input tree is  guaranteed  to be a binary search tree. Solution : class Codec: def serialize(self, root: Optional[TreeNode]) -> str:

  435 .  Non-overlapping Intervals Given an array of intervals  intervals  where  intervals[i] = [start i , end i ] , return  the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping .   Example 1: Input: intervals = [[1,2],[2,3],[3,4],[1,3]] Output: 1 Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping. Example 2: Input: intervals = [[1,2],[1,2],[1,2]] Output: 2 Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping. Example 3: Input: intervals = [[1,2],[2,3]] Output: 0 Explanation: You don't need to remove any of the intervals since they're already non-overlapping.   Constraints: 1 <= intervals.length <= 10 5 intervals[i].length == 2 -5 * 10 4  <= start i  < end i  <= 5 * 10 4 Solution : class Solution: def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: intervals.sort() ans = 0

  424 .  Longest Repeating Character Replacement You are given a string  s  and an integer  k . You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most  k  times. Return  the length of the longest substring containing the same letter you can get after performing the above operations .   Example 1: Input: s = "ABAB", k = 2 Output: 4 Explanation: Replace the two 'A's with two 'B's or vice versa. Example 2: Input: s = "AABABBA", k = 1 Output: 4 Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA". The substring "BBBB" has the longest repeating letters, which is 4.   Constraints: 1 <= s.length <= 10 5 s  consists of only uppercase English letters. 0 <= k <= s.length Solution :  class Solution: def characterReplacement(self, s: str, k: int) -> int: hm = {} ans = 0

417 .  Pacific Atlantic Water Flow There is an  m x n  rectangular island that borders both the  Pacific Ocean  and  Atlantic Ocean . The  Pacific Ocean  touches the island's left and top edges, and the  Atlantic Ocean  touches the island's right and bottom edges. The island is partitioned into a grid of square cells. You are given an  m x n  integer matrix  heights  where  heights[r][c]  represents the  height above sea level  of the cell at coordinate  (r, c) . The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is  less than or equal to  the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean. Return  a  2D list  of grid coordinates  result  where  result[i] = [r i , c i ]  denotes that rain water can flow from cell  (r i , c i )  to  both  the Pacific and Atlantic oceans .   Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],