My website

DP ```python class Solution: def canReach(self, s: str, a: int, b: int) -> bool: “”” tc O(N) sc O(N) dp[i]: start from idx= 0, there are at least 1 way to jump to s[i-1] “”” n = len(s) dp = [0] * (n+1) psum = [0] *(n+1) dp[1] = 1... [Read More]

DP solution ```python class Solution: def longestValidParentheses(self, s: str) -> int: “”” tc O(N) sc O(N) dp[i]: longest ValidParentheses ending at ith idex - only update dp when ) is encountered - check every two consecutive characters (1) s[i] == ) s[i-1] == ( then dp[i] = max(dp[i-2] +2,dp[i]) (2)... [Read More]

Brute Force way: Stack ```python class Solution: def minInsertions(self, s: str) -> int: “”” tc O(N) sc O(N) main idea: 1. each time encountered (, push into st; each time encountered ), chech st[-1] is empty, ( or ) if empty, need to insert ( if ( means we have... [Read More]

```python class Solution: def makeLargestSpecial(self, s: str) -> str: “"”tc O(N^2) sc O(N) 1. keep counting current 1 until cnt == 0, we find partition point, 2. push substring into stack 3. after loop is over, sort the substring and get lexicographically largest largest string “”” cnt,res = 0, []... [Read More]

Bit in place ```python class Solution: def shuffle(self, nums: List[int], n: int) -> List[int]: “"”tc O(N) sc O(1) main idea: bit manipulation + pair value in place overlap since nums[i] range [1,1000] => only occupy 10bits, we can use the feature a int number has 32 bits length to save... [Read More]