Home

1585. Check If String Is Transformable With Substring Sort Operations Given two strings s and t, you want to transform string s into string t using the following operation any number of times: Choose a non-empty substring in s and sort it in-place so the characters are in ascending order. For example, applying the operation on the underlined s...

85. Maximal Rectangle Solution 1 Convert the matrix to a list of histogram. Use 84. Largest Rectangle in Histogram Solution 2 - DP Reference Keep the left and right for each grid, which represent its leftmost and rightmost neighbours’ indexes. curr_left and curr_right represents the leftmost and rightmos...

84. Largest Rectangle in Histogram Solution - Memorization Reference Find the leftmost and rightmost index for each histogram. Use a memory array to ‘jump’ to the previous satisfied neighbour instead of looping through all neighbours. def largestRectangleArea(self, heights): """ :type heights: List[int] :rtype...

239. Sliding Window Maximum Solution Use a queue to maintain the maximum at each position. If a leftmost index in the queue is outside current window, pop it out. If the end of the queue is smaller than curr, it will no longer be the maximum in the following sliding window, pop it out. Push curr in. ...

42. Trapping Rain Water Solution The ‘height’ of the water that one col can trap is NOT decied by the col height. It is decided by the maximum height of neighbours to the left and right. Use two array to store the maximum height of neighbours for each col from left and right. The lower one of start[i] and end[i] decid...

72. Edit Distance Solution - DP Consider computing the distance between sub-strings, so that we only need to consider about the last character. The delete and insert operations are sure to make some differences. The replace operation will NOT make any difference when the last character is the same. An extra ...

299. Bulls and Cows Solution cow is related with the number of correct characters. If bull has used up the corrected characters, a misplaced correct character is not considered as cow. Count the number of bull. Count the sum of matched correct characters. cow = matched - bull def getHint(self, secret, g...

763. Partition Labels Solution For each character, store its starting point and end point. Loop through the string. Update the ending point whenever an encountered character ends later. When the visited character goes beyond the end, a new substring can start. We store the previous substring’s length. def partiti...