Top-Down:    n
                / \
            n-1  n-2
            / \   ...
            ...

    computed recursively

            
    Bottom-Up: 0 1 2 3 ... n
    
    computed iteratively

    def rob(self, nums: List[int]) -> int:

        n = len(nums)

        # Edge case: only 1 house
        # Without this, accessing nums[1] would cause IndexError
        if n == 1:
            return nums[0]

        # dp[i] = max money robbed from houses 0..i
        # Rule (2): "element i itself"
        dp = [0] * n                  # direct:
        dp[0] = nums[0]               # direct: max loop up to ith house
        dp[1] = max(nums[0], nums[1]) # direct: max loop up to 2nd house

        for i in range(2, n):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])

        return dp[n-1]

    def rob(nums: List[int]) -> int:

        n = len(nums)

        # dp[i] = max money robbed from the first i houses
        # Rule (1): "the first i elements"
        dp = [0] * (n+1)  # padding:
        dp[0] = 0         # padding: (empty case, max loot from no houses)
        dp[1] = nums[0]

        for i in range(2, n+1):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])

        return dp[n]

    def climbStairs(n: int) -> int:

        # dp[i] = ways to reach step i
        # Rule (1): "the first i elements"
        dp = [0] * (n+1)  # padding:
        dp[0] = 1         # padding: (ground case, 1 way: do nothing)
        dp[1] = 1 

        for i in range(2, n+1):
            dp[i] = dp[i-1] + dp[i-2]

        return dp[n]

    def climbStairs(n: int) -> int:
        
        # Edge cases:
        # Without this, setting dp[1] would cause IndexError
        if n == 1:
            return 1

        # dp[i] = ways to reach step (i+1)
        # Rule (2): "element i itself"
        dp = [0] * n  # direct
        dp[0] = 1     # direct: (ways to reach step 1)
        dp[1] = 2     # direct: (ways to reach step 2)

        for i in range(2, n):
            dp[i] = dp[i-1] + dp[i-2]

        return dp[n-1]

    def climbStairs(n: int) -> int:

        memo = {}

        def dfs(i: int) -> int:

            if i in memo:
                return memo[i]

            if i == 0:  # padding: ground, 1 way to do nothing
                return 1
            if i == 1:  # padded: first step
                return 1

            # recursive relation: sum of previous two steps
            memo[i] = dfs(i-1) + dfs(i-2)
            return memo[i]

        return dfs(n)

    def climbStairs(n: int) -> int:
        
        memo = {}

        def dfs(i: int) -> int:

            if i in memo:
                return memo[i]

            if i == 1:   # direct: 1st element
                return 1
            if i == 2:   # direct: 2nd element
                return 2

            # recursive relation: sum of previous two steps
            memo[i] = dfs(i-1) + dfs(i-2)
            return memo[i]

        return dfs(n)

    def climbStairs(n: int):

        # no length == 1 check, since using pad + 1st element
        # 1st element will always exist, pad is made up

        dp = [0] * (n + 1)  # padding:
        dp[0] = 1           # padding: (ground, 1 way to do nothing), 
                            # does not exist in original array

        dp[1] = 1           # padded: first element, n=0 -> dp[1]

        for i in range(2, n + 1):
            dp[i] = dp[i-1] + dp[i-2]

        return dp[n]

    def rob(nums):
        n = len(nums)

        # length == 1 check needed since using 1st + 2nd element
        # 2nd element may not exist
        if n == 1:
            return nums[0]

        dp = [0] * n                   # direct:
        dp[0] = nums[0]                # direct: 1st element
        dp[1] = max(nums[0], nums[1])  # direct: 2nd element

        for i in range(2, n):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])

        return dp[n-1]

    def climbStairs(n: int) -> int:

        # no length == 1 check, since using pad + 1st element
        # 1st element will always exist, pad is made up

        # padded variables
        prev2 = 1  # padding: ground (0 steps, 1 way to do nothing)
        prev1 = 1  # first step

        # no length check needed since prev1 and prev2 already cover n=1
        for i in range(2, n + 1):
            curr = prev1 + prev2
            prev2, prev1 = prev1, curr

        return prev1

    def rob(nums) -> int:
        n = len(nums)
        
        # length == 1 check needed since using 1st + 2nd element
        # 2nd element may not exist
        if n == 1:
            return nums[0]

        prev2 = nums[0]                # direct: first element
        prev1 = max(nums[0], nums[1])  # direct: second element

        for i in range(2, n):
            curr = max(prev1, prev2 + nums[i])
            prev2, prev1 = prev1, curr

        return prev1

    def maxProduct(nums: List[int]) -> int:
        n = len(nums)
        
        # Direct Variables -> rolling left and right products
        left_prod = right_prod = 1
        res = float('-inf')

        for i in range(n):
            # Build From Previous -> roll from left and right ends
            left_prod *= nums[i]
            right_prod *= nums[n-1-i]

            # Three Possibilities -> compare overall max
            res = max(res, left_prod, right_prod)

            # Direct Boundary -> reset rolling on zero
            if left_prod == 0:
                left_prod = 1
            if right_prod == 0:
                right_prod = 1

        return res

    def wordBreak(s: str, wordDict: List[str]) -> bool:
        n = len(s)
        
        # Direct Length -> empty string check
        if n == 0:
            return True

        word_set = set(wordDict)
        max_len = max(map(len, wordDict)) if wordDict else 0

        # Direct Variables -> initialize rolling DP window
        dp = [False] * (max_len + 1)
        dp[0] = True  # base case: empty string

        # Iterate -> 1 to n
        for i in range(1, n + 1):
            dp[i % (max_len + 1)] = False

            # Build From Previous -> look back up to max_len positions
            for l in range(1, min(i, max_len) + 1):
                # Three Possibilities -> valid segmentation from previous l positions
                if dp[(i - l) % (max_len + 1)] and s[i - l:i] in word_set:
                    dp[i % (max_len + 1)] = True
                    break  # early stop, valid segmentation found

        # Result -> final DP state
        return dp[n % (max_len + 1)]

    def coinChange(coins, amount):
        if amount == 0:
            return 0

        # Queue stores (remaining amount, coins used so far)
        queue = deque([(amount, 0)])
        visited = set([amount])  # memo: avoid revisiting same remaining amount

        while queue:
            rem, steps = queue.popleft()

            # Explore choices
            for coin in coins:
                next_rem = rem - coin

                # Early stop: minimal coins found
                if next_rem == 0:
                    return steps + 1

                # Valid state & not visited
                if next_rem > 0 and next_rem not in visited:
                    visited.add(next_rem)
                    queue.append((next_rem, steps + 1))

        # Impossible to reach target
        return -1

    def climbStairs(self, n: int) -> int:

        # Note:
        # Top Down DP (memoized recursion)
        # 0. Direct Length -> no need for len == n check, recursive padding boundary covers it
        # 1. Memo Check -> computed previously
        # 2. Pad Boundaries -> overshot case case
        # 3. Padded Boundary -> last element n
        # 3. Build From Previous -> grab from previous two steps and sum paths
        # 5. Memo Return -> return ways, calculated once
        # Result: Ways to climb from 0 to nth step

        memo = {}

        def dfs(i):

            # Memo Check -> computed previously
            if i in memo:
                return memo[i]
            
            # Pad Boundaries -> overshot case case
            if i > n:
                return 0

            # Padded Boundary -> last element n
            if i == n:
                return 1

            # Build From Previous -> grab from previous two steps and sum paths
            memo[i] = dfs(i + 1) + dfs(i + 2)

            # Memo return: return ways, calculated once
            return memo[i]

        # res -> ways to get from 0 to nth step
        res = dfs(0)

        # overall: time complexity O(n)
        # overall: space complexity O(n) (memo + recursion stack)
        return res

    def climbStairs(self, n: int) -> int:

        # Note:
        # Top Down DP (memoized recursion)
        # 0. Direct Length -> no need for len == 1 check, recursive padding boundary covers it
        # 1. Memo Check -> computed previously
        # 2. Pad Boundaries -> 0 ground case
        # 3. Padded Boundary -> 1st element
        # 4. Build From Previous -> grab from previous two steps and sum paths
        # 5. Memo return -> return ways, calculated once
        # Result: Ways to climb from 0 to nth step

        # Ways to climb from 0 to ith step
        memo = {}

        def dfs(i):

            # Memo Check -> computed previously
            if i in memo:
                return memo[i]
            
            # Pad Boundaries -> 0 ground case
            if i == 0:
                return 1

            # Padded Boundary -> 1st element
            if i == 1:
                return 1

            # Build From Previous -> grab from previous two steps and sum paths
            memo[i] = dfs(i - 1) + dfs(i - 2)

            # Memo return -> return ways, calculated once
            return memo[i]

        # res -> ways to climb from 0 to nth step
        res = dfs(n)

        # overall: time complexity O(n)
        # overall: space complexity O(n) (memo + recursion stack)
        return res

    def climbStairs(self, n: int) -> int:
        
        # Note:
        # Iterative Bottom Up Tabulation
        # 1. Pad Array -> 0 ground case, dp size (N+1)
        # 2. Padded -> grab 1st element
        # 3. Iterate -> 2 to n
        # 4. Build From Previous -> grab from previous two steps and sum paths
        # Result: ways to climb to nth step

        # Pad Array -> 0 ground case, dp size (N+1)
        dp = [0] * (n + 1)   # padding:
        dp[0] = 1            # padding: ground case, does not exist in array
        dp[1] = 1            # padded: first step

        # Iterate -> 2 to nth
        for i in range(2, n+1):
            # Build From Previous -> grab from previous two steps and sum paths
            dp[i] = dp[i-1] + dp[i-2]

        # res -> nth step
        res = dp[n]

        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return res

    def climbStairs(self, n: int) -> int:
        
        # Note:
        # Iterative Bottom Up Variables
        # 1. Pad Variables -> 0 ground case
        # 2. Padded -> grab 2st element
        # 3. Iterate -> 2 to n
        # 4. Build From Previous -> grab from previous two steps and sum paths
        # 5. Roll Variables -> Iterate Variables
        # Result: ways to climb to nth step

        # Pad Variables -> 0 ground case
        TwoPrev = 1  # padding:
        OnePrev = 1  # padded: 1st element

        # Iterate -> 2 to n
        for i in range(2, n+1):

            # Build From Previous -> grab from previous two steps and sum paths
            curr = TwoPrev + OnePrev

            # Slide Window -> Roll Variables
            TwoPrev, OnePrev = OnePrev, curr
        
        # res -> ways to climb to n step
        res = OnePrev

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return res

    def minCostClimbingStairs(self, cost: List[int]) -> int:
        
        # Note:
        # Top Down DP (memoized recursion)
        # 0. Direct Length -> no need for len == 1 check, recursive padding boundary covers it
        # 1. Memo Check -> computed previously
        # 2. Padding Boundary -> ground step 0
        # 3. Padded Boundary -> first element
        # 4. Build From Previous -> grab from previous two steps and sum paths
        # 5. Memo return -> return ways, calculated once
        # Result: min cost to reach n from last or 2nd to last step

        n = len(cost)

        memo = {}

        def dfs(i):

            # Memo Check -> computed previously
            if i in memo:
                return memo[i]

            # Padding Boundary -> ground step 0
            if i == 0:
                return 0

            # Padded Boundary -> first element
            if i == 1:
                return cost[0]

            # Build From Previous -> min cost to reach current step
            memo[i] = cost[i-1] + min(dfs(i-1), dfs(i-2))
            return memo[i]

        # res -> reach step n by coming from last two steps
        res = min(dfs(n), dfs(n-1))

        # overall: time complexity O(n)
        # overall: space complexity O(n) (memo + recursive stack)
        return res

    def minCostClimbingStairs(self, cost: List[int]) -> int:
        
        # Note:
        # Top Down DP (memoized recursion)
        # 0. Direct Length -> no need for len == 1 check, recursive direct boundary covers it
        # 1. Memo Check -> computed previously
        # 2. Direct Boundary -> 1st element
        # 3. Direct Boundary -> 2nd element
        # 4. Direct Build From Previous -> grab from previous two steps and sum paths
        # 5. Memo return -> return ways, calculated once
        # Result: min cost to reach n from last or 2nd to last step

        n = len(cost)

        memo = {}

        def dfs(i):

            # Memo Check -> computed previously
            if i in memo:
                return memo[i]

            # Direct Boundary -> 1st element
            if i == 0:
                return cost[0]

            # Direct Boundary -> 2nd element
            if i == 1:
                return cost[1]

            # Build -> min cost to reach + cost to continue
            memo[i] = cost[i] + min(dfs(i-1), dfs(i-2))
            return memo[i]

        # res -> reach n by continuing from nth or nth-1 step (since we step 1 or 2 steps)
        res = min(dfs(n-1), dfs(n-2))

        # overall: time complexity O(n)
        # overall: space complexity O(n) (memo + recursive stack)
        return res

    def minCostClimbingStairs(self, cost: List[int]) -> int:
        
        # Note:
        # Bottom Up Tabulation
        # 0. Direct Length -> no need for len == 1 check, description says min length == 2
        # 1. Direct Array -> 1st + 2nd element
        # 3. Iterate -> 2 to n-1
        # 4. Build From Previous -> grab from previous two steps and sum paths
        # Result: min cost to reach n via continuing from step n-1 or n-2

        # 0. Direct Length -> no need for len == 1 check, description says min length == 2

        n = len(cost)

        # Direct Array -> 1st + 2nd element
        dp = [0] * n
        dp[0], dp[1] = cost[0], cost[1]

        # Iterate -> steps 2 to n-1
        for i in range(2, n):

            # Build From Previous -> grab from previous two steps and sum paths
            dp[i] = cost[i] + min(dp[i-1], dp[i-2])

        # res -> min cost to reach n
        res = min(dp[n-1], dp[n-2])

        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return res

    def minCostClimbingStairs(self, cost: List[int]) -> int:
        
        # Note:
        # Bottom Up Variables
        # 0. Direct Length -> no need for len == 1 check, description says min length == 2
        # 1. Direct Variables -> 1st + 2nd element
        # 2. Iterate -> 2 to n-1
        # 3. Build From Previous -> grab from previous two steps and sum paths
        # 3. Roll Variables -> Iterate Variables
        # Result: min cost to reach n via continuing from last or 2nd to last step (n-1, or n-2)

        # 0. Direct Length -> no need for len == 1 check, description says min length == 2

        n = len(cost)

        # Direct Variables -> 1st + 2nd element
        prev2, prev1 = cost[0], cost[1]

        # Iterate -> 2 to n-1
        for i in range(2, n):
            
            # Build From Previous -> grab from previous two steps and sum paths
            curr = cost[i] + min(prev1, prev2)

            # Roll Variables -> Iterate Variables
            prev2, prev1 = prev1, curr

        # res -> min cost to reach n
        res = min(prev1, prev2)

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return res

    def tribonacci(self, n: int) -> int:

        # Note:
        # Top Down DP (memoized recursion)
        # 1. Memo Check -> computed previously
        # 2. Direct Boundary -> 1st element
        # 3. Direct Boundary -> 2nd element
        # 4. Direct Boundary -> 3rd element
        # 5. Build From Previous -> grab from previous two steps and sum paths
        # 6. Memo return -> return ways, calculated once
        # Result: T_i in Tribonacci sequence

        memo = {}

        def dfs(i):

            # Memo Check -> computed previously
            if i in memo:
                return memo[i]

            # Boundary -> 1st element
            if i == 0:
                return 0
            # Boundary -> 2nd element
            if i == 1:
                return 1
            # Boundary -> 3rd element
            if i == 2:
                return 1

            # Build From Previous -> grab from previous two steps and sum paths
            memo[i] = dfs(i-1) + dfs(i-2) + dfs(i-3)
            return memo[i]

        # res -> T_n value
        res = dfs(n)

        # overall: time complexity O(n)
        # overall: space complexity O(n) (memo + recursion stack)
        return res

    def tribonacci(n: int) -> int:

        # Note:
        # this is a unique case where Direct/N, requires an array of (N+1)
        # since we have 0 -> N fib solutions

        # Note:
        # Iterative Bottom Up Tabulation
        # 1. Direct Boundary -> need for len == 0, len == 1, and len == 2, as 3rd element may not exist
        # 2. Direct Array -> 1st, 2nd, and 3rd element
        # 3. Iterate -> 2 to n-1
        # 4. Iterate -> 3 to n
        # 5. Build From Previous -> sum previous three DP entries
        # Result: T_n in Tribonacci sequence

        # Direct Boundary -> len == 0, len == 1, and len == 2, as 3rd element may not exist
        if n == 0:
            return 0
        if n == 1:
            return 1

        # Direct Array -> 1st, 2nd, and 3rd element
        dp = [0] * (n+1)
        dp[0], dp[1], dp[2] = 0, 1, 1

        # Iterate -> 3 to n
        for i in range(3, n+1):

            # Build From Previous -> sum of last three
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

        # res -> nth tribonacci
        res = dp[n]

        # overall: time complexity O(n)
        # overall: space complexity O(n) (memo + recursive stack)
        return res

    def tribonacci(self, n: int) -> int:

        # Note:
        # this is a unique case where Direct/N, requires an array of (N+1)
        # since we have 0 -> N fib solutions

        # Note:
        # Iterative Bottom Up Variables
        # 1. Direct Boundary -> need len == 1 check, elements 2 and 3 may not exist
        # 2. Direct Variables -> 1st + 2nd + 3rd elements
        # 3. Iterate -> 3 to n
        # 4. Build From Previous -> grab from previous two steps and sum paths
        # 5. Roll Variables -> Iterate Variables
        # Result: T_n in Tribonacci sequence

        # Direct Boundary -> need len == 1 check, elements 2 and 3 may not exist
        if n == 0:
            return 0
        if n == 1:
            return 1 

        # Direct Variables -> 1st + 2nd + 3rd elements
        ThreePrev, TwoPrev, OnePrev = 0, 1, 1

        # Iterate -> 3 to n
        for i in range(3, n+1):

            # Build From Previous -> grab from previous two steps and sum paths
            curr = ThreePrev + TwoPrev + OnePrev

            # Roll Variables -> Iterate Variables
            ThreePrev, TwoPrev, OnePrev = TwoPrev, OnePrev, curr

        # res -> nth tribonacci
        res = OnePrev

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return res

    def rob(self, nums: List[int]) -> int:
        
        # Note:
        # Top down recursive with memoization
        # 0. Direct Length -> no need for len == 1 check, recursive padding boundary covers it
        # 1. Memo Check -> computed previously
        # 2. Direct Boundary -> 1st element
        # 3. Direct Boundary -> 2nd element
        # 3. Build From Previous -> grab from previous two steps and sum paths
        # Result: max loop from first to last house

        n = len(nums)

        memo = {}

        def dfs(i):

            # Memo Check -> computed previously
            if i in memo:
                return memo[i]

            # Direct Boundary -> 1st element
            if i == 0:
                return nums[0]

            # Direct Boundary -> 2nd element
            if i == 1:
                return max(nums[0], nums[1])
            
            # Direct Build From Previous -> grab from previous two steps and sum paths
            # choose max between rob or skipping current house
            memo[i] = max(nums[i] + dfs(i-2), dfs(i-1))
            return memo[i]

        # res -> max loot for nth house
        res = dfs(n-1)

        # overall: time complexity O(n)
        # overall: space complexity O(n) (memo + recursion stack)
        return res

    def rob(self, nums: List[int]) -> int:
        
        # Note:
        # Bottom Up Tabulation
        # 0. Direct Length -> need for len == 1 check, 2nd element may not exist
        # 1. Direct Array -> 1st + 2nd element
        # 2. Iterate -> 2 to n-1
        # 3. Build From Previous -> grab from previous two steps and sum paths
        # Result: max loot from nth house

        n = len(nums)

        # Direct Length -> need for len == 1 check, 2nd element may not exist
        if n == 1:
            return nums[0]

        # Direct Array -> 1st + 2nd element
        dp = [0] * n
        dp[0], dp[1] = nums[0], max(nums[0], nums[1])

        # Iterate -> 2 to n-1
        for i in range(2, n):

            # Build From Previous -> grab from previous two steps and sum paths
            # choose max between rob or skipping current house
            dp[i] = max(nums[i] + dp[i-2], dp[i-1])

        # res -> max loot at nth house
        res = dp[n-1]

        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return res

    def rob(self, nums: List[int]) -> int:

        # Note:
        # Bottom Up Variables
        # 0. Direct Length -> need for len == 1 check, 2nd element may not exist
        # 1. Direct Variables -> 1st + 2nd element
        # 2. Iterate -> 2 to n-1
        # 3. Build From Previous -> grab from previous two steps and sum paths
        # 4. Roll Variables -> Iterate Variables
        # Result: max loot first to last house

        n = len(nums)

        # Direct Length -> need for len == 1 check, 2nd element may not exist
        if n == 1:
            return nums[0]

        # Direct Variables -> 1st + 2nd element
        prev2, prev1 = nums[0], max(nums[0], nums[1])

        # Iterate -> 2 to n-1
        for i in range(2, n):

            # Build From Previous -> grab from previous two steps and sum paths
            curr = max(prev1, nums[i] + prev2)

            # Roll Variables -> Iterate Variables
            prev2, prev1 = prev1, curr

        # res -> max loot at nth house
        res = prev1

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return res

    def rob(self, nums: List[int]) -> int:

        # Note:
        # Top down (recursive with memoization)
        # 0. Direct Length -> need for len == 1 check, 2nd element may not exist
        # 1. Memo Check -> computed previously
        # 2. Direct Boundary -> 1st + 2nd element
        # 3. Build From Previous -> grab from previous two steps and sum paths
        # 4. Handle circular constraint -> cannot rob both first and last
        # Result: max loot for circular house array

        n = len(nums)

        # Direct Length -> need for len == 1 check, 2nd element may not exist
        if n == 1:
            return nums[0]

        def rob_range(start, end):

            memo = {}

            def dfs(i):

                # Memo Check -> computed previously
                if i in memo:
                    return memo[i]

                # Direct Boundary -> i == 0 (in subarray)
                if i == start:
                    return nums[i]

                # Direct Boundary -> i == 1 (in subarray)
                if i == start + 1:
                    return max(nums[i], nums[i - 1])

                # Build From Previous -> grab from previous two steps and sum paths
                memo[i] = max(nums[i] + dfs(i-2), dfs(i-1))
                return memo[i]

            # res -> max loot at last house in subarray
            return dfs(end)

        # Handle circular constraint -> cannot rob both first and last
        res1 = rob_range(0, n-2)
        res2 = rob_range(1, n-1)

        # res -> max loot from circular houses
        res = max(res1, res2)

        # overall: time complexity O(n)
        # overall: space complexity O(n) (memo + recursion stack)
        return res

    def rob(self, nums: List[int]) -> int:
        
        # Note:
        # Bottom up array
        # 0. Direct Length -> need for len == 1 check, 2nd element may not exist
        # 1. Direct Length (subarray) -> need for len == 1 check, 2nd element may not exist
        # 2. Direct Array -> 1st + 2nd element
        # 3. Iterate -> 2 to numHouses-1
        # 4. Build From Previous -> grab from previous two steps and sum paths
        # 5. Handle circular constraint -> 2 subsets to break circular array
        # Result: max loot from circular houses array

        n = len(nums)

        # Direct Length -> need for len == 1 check, 2nd element may not exist
        if n == 1:
            return nums[0]

        def rob_range(start, end):

            # Direct Length -> need for len == 1 check, 2nd element may not exist
            m = end - start + 1
            if m == 1:
                return nums[start]

            # Direct Array -> 1st + 2nd element
            dp = [0] * m
            dp[0] = nums[start]
            dp[1] = max(nums[start], nums[start + 1])

            # Iterate -> 2 to m-1
            for i in range(2, m):
                j = start + i
                # Build From Previous -> grab from previous two steps and sum paths
                # choose max between rob or skipping current house
                dp[i] = max(nums[j] + dp[i-2], dp[i-1])

            # res -> max loot at last house in subarray
            return dp[m-1]


        # Handle circular constraint -> cannot rob both first and last
        res1 = rob_range(0, n-2)
        res2 = rob_range(1, n-1)

        # res -> max loot from circular houses
        res = max(res1, res2)

        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return res

    def rob(self, nums: List[int]) -> int:

        # Note:
        # Bottom up variables
        # 0. Direct Length -> need for len == 1 check, 2nd element may not exist
        # 1. Direct Length (subarray) -> need for len == 1 check, 2nd element may not exist
        # 2. Direct Variables -> 1st + 2nd element
        # 3. Iterate -> 2 to numHouses-1
        # 4. Build From Previous -> grab from previous two steps and sum paths
        # 5. Roll Variables -> Iterate Variables
        # 6. Handle circular constraint -> cannot rob both first and last
        # Result: max loot from circular houses

        n = len(nums)

        # Direct Length -> need for len == 1 check, 2nd element may not exist
        if n == 1:
            return nums[0]

        def rob_range(start, end):

            # Direct Length -> need for len == 1 check, 2nd element may not exist
            m = end - start + 1
            if m == 1:
                return nums[start]

            # Direct Variables -> 1st + 2nd element
            TwoPrev = nums[start]
            OnePrev = max(nums[start], nums[start+1])

            # Iterate -> 2 to m-1
            for i in range(2, m):
                j = start + i
                # Build From Previous -> grab from previous two steps and sum paths
                curr = max(nums[j] + TwoPrev, OnePrev)

                # Roll Variables -> Iterate Variables
                TwoPrev, OnePrev = OnePrev, curr

            # res -> max loot at last house in subarray
            res = OnePrev
            return res

        # Handle circular constraint -> cannot rob both first and last
        res1 = rob_range(0, n-2)
        res2 = rob_range(1, n-1)

        # res -> max loot from circular houses
        res = max(res1, res2)

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return res

    def longestPalindrome(self, s: str) -> str:
        
        # INCORRECT:
        # did not create expandedStr
        # did not solve odd vs even palindrome problem
        # missing:
        # expandedStr = "#".join(f"^{s}$")
        
        center = 0
        right = 0
        n = len(s)
        p = [0] * n

        for i in range(1, n-1):
            
            # 1 
            mirror = (2*center) - i

            # 2 
            if i < right:
                p[i] = min(right-i, p[mirror])

            # 3
            while s[i + p[i] + 1] == s[i - p[i] - 1]:
                p[i] += 1

            # 4
            if i + p[i] > right:
                center = i
                right = i + p[i]
        
        (maxRadius, center) = max((maxRadius, i) for (i, maxRadius) in enumerate(p))
        start = (center-maxRadius) // 2 

        return s[start:start+maxRadius]

    def longestPalindrome(self, s: str) -> str:
        
        def expandAroundCenter(left, right):
            while left >= 0 and right < n and s[left] == s[right]:
                left -= 1
                right += 1

            # INCORRECT:
            # defined list instead of slicing
            # should be: s[left+1:right]
            return s[left+1, right]
        
        n = len(s)
        maxPalin = ""

        for i in range(n):
            oddPalin = expandAroundCenter(i, i)
            evenPalin = expandAroundCenter(i, i+1)

            if len(oddPalin) > len(maxPalin):
                maxPalin = oddPalin
            if len(evenPalin) > len(maxPalin):
                maxPalin = evenPalin
                
        return maxPalin

    def longestPalindrome(self, s: str) -> str:
        
        expandedStr = "#".join(f"^{s}$")
        n = len(expandedStr)
        p = [0] * n
        center = 0
        right = 0

        # INCORRECT:
        # iteration will also expand from the sentinals '^' and '$'
        for i in range(n):

            # grab mirror
            mirror = (2*center)-i

            # validate mirror
            if i < right:
                p[i] = min(p[mirror], (right-i))

            # expand
            # INCORRECT:
            # due to iteration, expansion is not guaranteed and prevent
            # out of bounds grab, since we are missing the eventual
            # '^' != '$'
            while expandedStr[i - p[i] - 1] == expandedStr[i + p[i] + 1]:
                p[i] += 1

            # find new right most
            if p[i] + i > right:
                center = i
                right = p[i] + i

        # translate back to height
        maxRadi, center = max((maxRadi, center) for (center, maxRadi) in enumerate(p))

        startIndex = (center-maxRadi)//2


        return s[startIndex:startIndex+maxRadi]

    def longestPalindrome(self, s: str) -> str:
        
        expandedStr = "#".join(f"^{s}$")
        n = len(expandedStr)
        p = [0] * n
        center = 0
        right = 0

        for i in range(1, n-1):

            # grab mirror
            mirror = (2*center)-i

            # validate mirror
            if i < right:
                p[i] = min(p[mirror], (right-i))

            # expand
            while expandedStr[i - p[i] - 1] == expandedStr[i + p[i] + 1]:
                p[i] += 1

            # find new right most
            if p[i] + i > right:
                center = i
                right = p[i] + i

        # translate back to height
        # INCORRECT:
        # should be 
        # enumerate(p)
        # instead of p.enumerate()
        maxRadi, center = max((maxRadi, center) for (center, maxRadi) in p.enumerate())

        startIndex = (center-maxRadi)//2


        return s[startIndex:startIndex+maxRadi]

    def longestPalindrome(self, s: str) -> str:

        # Note: 
        # Preprocessing with #, ^, and $:
        # '#': ensures uniform expansion, for both odd and even length palindromes
        # '^' and '$': sentinel characters don't match valid input characters, serve as true start and end markers
        # '#': ensures all palindromes start and end with '#'
        # '#': occur on odd indexes

        # Mapping:
        # we can map odd '#' indexes to their even character:
        # mapping '#' at index 1 to char pair 'a' at index 2, to original 'a' at index 0
        # [ ^ # a # b # a # $ ] -> [ a b a ]    via : originalStart = (expandedCenter - radius) / 2
        #   0 1 2 3 4 5 6 7 8        0 1 2      thus: originalStart = (4 - 3) / 2 = 0
        
        # Boundary expansion: 
        # For any index i, center of palindrome at i can either be: 
        # - character from the original string
        # - placeholder '#'
        # Center definition allows even length palindromes such as "abba", see below,
        # to have a single middle point, allowing the same expanding logic 
        # for even and odd strings for palindrome validation

        # Ex:
        # ^ # a # b # b # a # $    || new string len 11,
        # 0 1 2 3 4 5 6 7 8 9 10   ||
        #           ^              || index 5 center for even length "abba"

        # index 1 palindrome: "#"
        # index 2 palindrome: "#a#"
        # index 5 palindrome: "#a#b#b#a#"
        # etc...

        expandedStr = "#".join(f"^{s}$")
        n = len(expandedStr)

        # Right Most Palindrome and Mirror Trick: 
        # Iteration tracks the right boundary for the current farthest right palindromic substring, 
        # which allows us to take advantage of the mirror radius trick.
        # It speeds up palindrome expansion by starting the current palindrome radius
        # at the radius value of its mirror

        # p[i]: radius of palindrome centered at some index i
        p = [0] * n

        # mirror radius validation: tracking right boundary
        # right: right boundary of the current right most palindrome
        right = 0

        # mirror radius validation: tracking center of right most in order to calculate mirror index
        # center: center index of the current right most palindrome
        center = 0 

        # iteration range ignores sentinel indexes 0 and (n-1): ^ and $
        # i: center of current palindrome
        # time complexity: iterate over list of n length O(n)
        for i in range(1, n - 1):

            # mirror:
            # i is current index being processed
            # i is to the right of center and has a mirror to the left of center
            # ex: center = 6, i = 7 => mirror = (2 * 6) - 7 = 5
            mirror = (2 * center) - i 

            # mirror radius validation:
            # if i lies within bounds of the right most palindrome,
            # the right most palindrome symmetry guarantees that the palindrome radius
            # for the mirror of i, is applicable to i as well,
            # while within the bounds of the right most palindrome
            if i < right:

                # mirror radius is either:
                # - less than the distance between i and right bound,
                #   in which case all of the radius is valid
                # - exceeds bounds and is farther than right bound,
                #   in which case only the radius up until the right bound is valid
                
                # i radius is thus, bounded by minimum between: 
                # - mirror radius
                # - distance from i to the right bound
                p[i] = min(right - i, p[mirror])

            # assumption: if valid mirror, we pre-set p[i] to p[mirror]
            # now expand: expand radius p[i] until palindromic status is broken
            while expandedStr[i + p[i] + 1] == expandedStr[i - p[i] - 1]:
                p[i] += 1

            # p[i]: radius for palindrome at i
            # i: center for palindrome at i
            # check: if we have a new right most boundary, update center and right 
            if i + p[i] > right:
                right = i + p[i]
                center = i

        # expandedStr iteration complete:
        # p[] stores radius of palindrome centered at each index

        # scan p[] grabbing max palindrome radius alongside its center
        maxRadius, centerIndex = max((palindromeRadius, i) for (i, palindromeRadius) in enumerate(p))

        # Note:
        # index and radius are relative to expandedStr, not the original string
        # thus, we need to translate to original string indexes

        # Notice, how in the expanded string, 
        #  - all original characters are on even index
        #  - all original characters have matching # on the left odd index

        # abba =>  ^ # a # b # b # a # $   | a=2, b=4, b=6, a=8
        # 0123 =>  0 1 2 3 4 5 6 7 8 9 10  | #=1, #=3, #=5, #=7

        # aba =>   ^ # a # b # a # $       | a=2, b=4, a=6
        # 012 =>   0 1 2 3 4 5 6 7 8       | #=1, #=3, #=5

        # any palindrome will always end with a '#'.
        # so if we divide the starting odd position by 2, it will always map
        # to an original character.
        # so an easy translation formula is:

        start = (centerIndex - maxRadius) // 2
        
        # splice longest substring

        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return s[start: start + maxRadius]

    def longestPalindrome(self, s: str) -> str:

        # expand from a given left and right while 
        # maintaining palindrome property
        def expandAroundCenter(left, right):
            while left >= 0 and right < n and s[left] == s[right]:
                left -= 1
                right += 1

            # curr iteration is not valid:
            # ignore left: incrementing index
            # ignore right: noninclusive right slicing
            return s[left+1:right] 
         
        n = len(s)
        maxPalindrome = ""

        # time complexity: iterate over list of n length O(n)
        for i in range(n):
            # odd expansion, centered at i
            oddPalindrome = expandAroundCenter(i, i)      
            # even expansion, centered at i and i + 1
            evenPalindrome = expandAroundCenter(i, i+1)

            # update longest
            if len(oddPalindrome) > len(maxPalindrome):
                maxPalindrome = oddPalindrome
            if len(evenPalindrome) > len(maxPalindrome):
                maxPalindrome = evenPalindrome

        # overall: time complexity O(n^2)
        # overall: space complexity O(1)
        return maxPalindrome

        def longestPalindrome(self, s: str) -> str:
        
        n = len(s)
        dp = [[False]*n for _ in range(n)]
        start, max_len = 0, 1

        for i in range(n):
            dp[i][i] = True

        for length in range(2, n+1):  # substring length
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j]:
                    if length == 2 or dp[i+1][j-1]:
                        dp[i][j] = True
                        if length > max_len:
                            start, max_len = i, length

        return s[start:start+max_len]

    def countSubstrings(self, s: str) -> int:
        n = len(s)
        count = 0

        # helper: expand from center
        def expand(l: int, r: int) -> int:
            local_count = 0
            while l >= 0 and r < n and s[l] == s[r]:
                local_count += 1   # found a palindrome
                l -= 1
                r += 1
            return local_count

        # expand around all possible centers
        for i in range(n):
            count += expand(i, i)     # odd-length palindromes
            count += expand(i, i + 1) # even-length palindromes

        return count

    def countSubstrings(self, s: str) -> int:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        count = 0

        # single characters
        for i in range(n):
            dp[i][i] = True
            count += 1

        # substring lengths 2 -> n
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j]:
                    if length == 2 or dp[i + 1][j - 1]:
                        dp[i][j] = True
                        count += 1

        return count

    def numDecodings(self, s: str) -> int:

        # Note:
        # Top Down DP (recursive with memoization)
        # 0. Direct Length -> no need for len == 1 check, recursive padding boundary covers it
        # 1. Memo Check -> computed previously
        # 2. Direct Boundary -> 1st element: empty string
        # 3. Direct Boundary -> 2nd element: first char
        # 4. Build From Previous -> grab from previous two steps and sum paths
        # Result: total decode ways from start (0) to end (n-1)

        n = len(s)

        memo = {}

        def dfs(i):

            # Memo Check -> computed previously
            if i in memo:
                return memo[i]

            # Direct Boundary -> 1st element: empty string
            if i < 0:
                return 1

            # Direct Boundary -> 2nd element: first char
            if i == 0:
                return 1 if s[0] != '0' else 0

            count = 0

            # Build From Previous -> grab from previous two steps and sum paths
            
            # 'How many total ways can I decode up to here if I decide to treat 
            # the current group as a valid single or valid double digit?'
            # Add corresponding counts from single: i-1 and double: i-2

            # check previous char, if single is valid
            if s[i] != '0':
                count += dfs(i-1)
            
            # check double via previous char, if double is valid
            two_digit = int(s[i-1:i+1])
            if 10 <= two_digit <= 26:
                count += dfs(i-2)

            memo[i] = count
            return memo[i]

        # res -> number of decode ways for nth
        res = dfs(n-1)

        # overall: time complexity
        # overall: space complexity
        return res

    def numDecodings(self, s: str) -> int:

        # Note:
        # Iteration here is unique here because we cant initialize/skip i = 1, 
        # because it introduces the first valid two digit choice. 
        # If we jumped directly to i = 2, we’d miss the case where the answer 
        # depends entirely on that first double digit decode.

        # Note:
        # Bottom Up DP
        # 0. Direct Length -> need for len == 1 check, 2nd element/first char may not exist
        # 1. Direct Array -> 1st element
        # 2. Iterate -> 1 to n-1
        # 3. Build From Previous -> grab from previous two steps and sum paths
        # Result: total decode ways nth

        n = len(s)

        # Direct Length -> need for len == 0 check, 2nd element/first char may not exist
        if not s:
            return 0

        # Direct Array -> 1st element
        dp = [0] * n
        dp[0] = 1 if s[0] != '0' else 0

        # Iterate -> 1 to n-1
        for i in range(1, n):

            # Build From Previous -> grab from previous two steps and sum paths

            # 'How many total ways can I decode up to here if I decide to treat 
            # the current group as a valid single or valid double digit?'
            # Add corresponding counts from single: i-1 and double: i-2

            # check previous char, if single is valid
            if s[i] != '0':
                dp[i] += dp[i-1]

            # check double via previous char, if double is valid
            two_digit = int(s[i-1:i+1])
            if 10 <= two_digit <= 26:
                dp[i] += dp[i-2] if i >= 2 else 1

        # res -> number of decode ways for nth
        res = dp[n-1]

        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return res

    def numDecodings(self, s: str) -> int:

        # Note:
        # Iteration here is unique here because we cant initialize/skip i = 1, 
        # because it introduces the first valid two digit choice. 
        # If we jumped directly to i = 2, we’d miss the case where the answer 
        # depends entirely on that first double digit decode.

        # Note:
        # Bottom-up DP with space optimization
        # 0. Direct Length -> need for len == 0 check, 2nd element/first char, maybe not exist
        # 1. Direct Variables -> 1st element
        # 2. Iterate -> 1 to n-1
        # 3. Build From Previous -> grab from previous two steps and sum paths
        # 4. Roll Variables -> Iterate Variables
        # Result -> total decode ways nth

        # Direct Length -> need for len == 0 check, 2nd element/first char, maybe not exist
        if not s:
            return 0

        n = len(s)

        # Direct Variables -> 1st element
        prev2 = 0 
        prev1 = 1 if s[0] != '0' else 0

        # Iterate -> 1 to n-1
        for i in range(1, n):

            curr = 0

            # Build From Previous -> grab from previous two steps and sum paths

            # 'How many total ways can I decode up to here if I decide to treat 
            # the current group as a valid single or valid double digit?'
            # Add corresponding counts from single: i-1 and double: i-2

            # check previous char, if single is valid
            if s[i] != '0':
                curr += prev1

            # decode ignoring double digit
            two_digit = int(s[i-1:i+1])
            if 10 <= two_digit <= 26:
                curr += prev2 if i >= 2 else 1

            # Roll Variables -> Iterate Variables
            prev2, prev1 = prev1, curr

        # res -> number of decode ways for nth
        res = prev1

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return res

    def coinChange(self, coins: List[int], amount: int) -> int:

        # Note:
        # Top down (recursive with memoization)
        # 0. Direct Length -> no need for len == 1 check, recursive padding boundary covers it
        # 1. Memo Check -> computed previously
        # 2. Boundary Check -> exact match
        # 3. Build From Previous -> grab from previous two steps and sum paths
        # 4. Early Prune -> check if current coin leads to possible, else skip
        # Result: min coins to reach amount if possible 

        sentinel = float('inf')

        memo = {}

        def dfs(curr_amount) -> int:

            # Memo Check -> computed previously
            if curr_amount in memo:
                return memo[curr_amount]
            
            # Boundary Check -> exact match
            if curr_amount == 0:
                return 0

            curr_min = sentinel
            
            # Build From Previous -> grab from previous two steps and sum paths
            for coin in coins:

                # Early Prune -> check if current coin leads to possible, else skip
                new_remaining = curr_amount - coin
                if new_remaining >= 0:

                    # check if new min coin beats previous
                    use_coin = dfs(new_remaining)
                    curr_min = min(curr_min, use_coin+1)

            # res -> min coins to reach current amount
            memo[curr_amount] = curr_min
            return memo[curr_amount]

        # Result -> remaining amount set to full, grab min number of coins
        res = dfs(amount)

        # overall: time complexity 
        # overall: space complexity
        return -1 if res == float('inf') else res