"""
LC 70 — Climbing Stairs
=======================

You are climbing a staircase. It takes `n` steps to reach the top.
Each time you can either climb 1 or 2 steps.
In how many distinct ways can you climb to the top?

Examples
--------
```text
Input:  n = 2
Output: 2
Explanation: 1+1, 2

Input:  n = 3
Output: 3
Explanation: 1+1+1, 1+2, 2+1
```

Constraints
-----------
- 1 <= n <= 45
"""

from functools import lru_cache


class Solution:
    # Approach 1: Recursion with memoization — O(n) time, O(n) space
    def climbStairs(self, n: int) -> int:
        # dp(i) = ways to reach step i = dp(i-1) + dp(i-2) (Fibonacci-like)
        @lru_cache(maxsize=None)
        def dp(i: int) -> int:
            if i <= 1:
                return 1
            return dp(i - 1) + dp(i - 2)
        return dp(n)

    # Approach 2: Bottom-up DP — O(n) time, O(n) space
    def climbStairs_dp(self, n: int) -> int:
        # Bottom-up: fill table[i] = table[i-1] + table[i-2]
        if n <= 1:
            return 1
        table = [0] * (n + 1)
        table[0], table[1] = 1, 1
        for i in range(2, n + 1):
            table[i] = table[i - 1] + table[i - 2]
        return table[n]

    # Approach 3: Space-optimized — O(n) time, O(1) space
    def climbStairs_opt(self, n: int) -> int:
        # Space-optimized: only keep last two values
        a, b = 1, 1
        for _ in range(2, n + 1):
            a, b = b, a + b
        return b


if __name__ == "__main__":
    sol = Solution()
    assert sol.climbStairs(1) == 1
    assert sol.climbStairs(2) == 2
    assert sol.climbStairs(3) == 3
    assert sol.climbStairs(5) == 8
    assert sol.climbStairs_dp(3) == 3
    assert sol.climbStairs_opt(3) == 3
    print("All tests passed.")

"""
LC 322 — Coin Change
=====================

You are given an integer array `coins` representing coins of different denominations
and an integer `amount` representing a total amount of money.
Return the fewest number of coins needed to make up that amount.
If that amount cannot be made up, return -1.
You may assume you have an infinite number of each coin.

Examples
--------
```text
Input:  coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 5 + 5 + 1 = 11

Input:  coins = [2], amount = 3
Output: -1

Input:  coins = [1], amount = 0
Output: 0
```

Constraints
-----------
- 1 <= coins.length <= 12
- 1 <= coins[i] <= 2^31 - 1
- 0 <= amount <= 10^4
"""

from typing import List
from functools import lru_cache


class Solution:
    # Approach 1: Top-down memoization — O(amount * n) time, O(amount) space
    def coinChange(self, coins: List[int], amount: int) -> int:
        # dp(rem) = 1 + min(dp(rem-c) for each coin c); base: dp(0)=0
        @lru_cache(maxsize=None)
        def dp(rem: int) -> int:
            if rem == 0:
                return 0
            if rem < 0:
                return float('inf')
            return min(1 + dp(rem - c) for c in coins)

        result = dp(amount)
        return result if result != float('inf') else -1

    # Approach 2: Bottom-up DP — O(amount * n) time, O(amount) space
    def coinChange_dp(self, coins: List[int], amount: int) -> int:
        # dp[i] = min coins to make amount i; try each coin and take minimum
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        for i in range(1, amount + 1):
            for c in coins:
                if c <= i:
                    dp[i] = min(dp[i], 1 + dp[i - c])
        return dp[amount] if dp[amount] != float('inf') else -1


if __name__ == "__main__":
    sol = Solution()
    assert sol.coinChange([1, 2, 5], 11) == 3
    assert sol.coinChange([2], 3) == -1
    assert sol.coinChange([1], 0) == 0
    assert sol.coinChange([1, 5, 11], 11) == 1
    assert sol.coinChange_dp([1, 2, 5], 11) == 3
    assert sol.coinChange_dp([2], 3) == -1
    print("All tests passed.")

"""
LC 377 — Combination Sum IV
=============================

Given an array of distinct integers `nums` and a target integer `target`,
return the number of possible combinations that add up to `target`.
The order of the combination matters (permutations count separately).

Examples
--------
```text
Input:  nums = [1, 2, 3], target = 4
Output: 7
Explanation:
  (1, 1, 1, 1)
  (1, 1, 2)
  (1, 2, 1)
  (1, 3)
  (2, 1, 1)
  (2, 2)
  (3, 1)

Input:  nums = [9], target = 3
Output: 0
```

Constraints
-----------
- 1 <= nums.length <= 200
- 1 <= nums[i] <= 1000
- All elements of nums are unique
- 1 <= target <= 1000
"""

from typing import List
from functools import lru_cache


class Solution:
    # Approach 1: Top-down memoization — O(target * n) time, O(target) space
    def combinationSum4(self, nums: List[int], target: int) -> int:
        # dp(rem) = sum of dp(rem-num) for each num <= rem; order matters (permutations)
        @lru_cache(maxsize=None)
        def dp(rem: int) -> int:
            if rem == 0:
                return 1
            return sum(dp(rem - num) for num in nums if num <= rem)

        return dp(target)

    # Approach 2: Bottom-up DP — O(target * n) time, O(target) space
    def combinationSum4_dp(self, nums: List[int], target: int) -> int:
        # dp[i] = number of ordered combinations summing to i
        dp = [0] * (target + 1)
        dp[0] = 1
        for i in range(1, target + 1):
            for num in nums:
                if num <= i:
                    dp[i] += dp[i - num]
        return dp[target]


if __name__ == "__main__":
    sol = Solution()
    assert sol.combinationSum4([1, 2, 3], 4) == 7
    assert sol.combinationSum4([9], 3) == 0
    assert sol.combinationSum4_dp([1, 2, 3], 4) == 7
    assert sol.combinationSum4_dp([9], 3) == 0
    print("All tests passed.")

"""
LC 91 — Decode Ways
====================

A message containing letters A-Z can be encoded into numbers using:
  'A' -> "1", 'B' -> "2", ..., 'Z' -> "26"

Given a string `s` containing only digits, return the number of ways to decode it.

Examples
--------
```text
Input:  s = "12"
Output: 2
Explanation: "AB" (1 2) or "L" (12)

Input:  s = "226"
Output: 3
Explanation: "BZ" (2 26), "VF" (22 6), "BBF" (2 2 6)

Input:  s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero.
```

Constraints
-----------
- 1 <= s.length <= 100
- s contains only digits
- s may contain leading zeros
"""

from functools import lru_cache


class Solution:
    # Approach 1: Top-down memoization — O(n) time, O(n) space
    def numDecodings(self, s: str) -> int:
        # dp(i): ways to decode s[i:]; '0' has 0 ways; two-digit check for 10-26
        @lru_cache(maxsize=None)
        def dp(i: int) -> int:
            if i == len(s):
                return 1
            if s[i] == '0':
                return 0
            result = dp(i + 1)
            if i + 1 < len(s) and int(s[i:i + 2]) <= 26:
                result += dp(i + 2)
            return result

        return dp(0)

    # Approach 2: Bottom-up DP — O(n) time, O(n) space
    def numDecodings_dp(self, s: str) -> int:
        # Bottom-up from end; dp[i] = dp[i+1] + dp[i+2] if two-digit valid
        n = len(s)
        dp = [0] * (n + 1)
        dp[n] = 1
        for i in range(n - 1, -1, -1):
            if s[i] != '0':
                dp[i] = dp[i + 1]
                if i + 1 < n and int(s[i:i + 2]) <= 26:
                    dp[i] += dp[i + 2]
        return dp[0]

    # Approach 3: Space-optimized — O(n) time, O(1) space
    def numDecodings_opt(self, s: str) -> int:
        # Space-optimized: next1=dp[i+1], next2=dp[i+2]; roll forward
        n = len(s)
        next2, next1 = 1, 1  # dp[n+1]=1 (sentinel), dp[n]=1 (base case)
        for i in range(n - 1, -1, -1):
            curr = 0
            if s[i] != '0':
                curr = next1
                if i + 1 < n and int(s[i:i + 2]) <= 26:
                    curr += next2
            next2, next1 = next1, curr
        return next1


if __name__ == "__main__":
    sol = Solution()
    assert sol.numDecodings("12") == 2
    assert sol.numDecodings("226") == 3
    assert sol.numDecodings("06") == 0
    assert sol.numDecodings("0") == 0
    assert sol.numDecodings_dp("226") == 3
    assert sol.numDecodings_opt("226") == 3
    print("All tests passed.")

"""
LC 198 — House Robber
======================

You are a professional robber planning to rob houses along a street.
Each house has a certain amount of money stashed. Adjacent houses have
security systems connected — you cannot rob two adjacent houses.

Given an integer array `nums` representing the amount of money of each house,
return the maximum amount of money you can rob tonight without alerting the police.

Examples
--------
```text
Input:  nums = [1, 2, 3, 1]
Output: 4
Explanation: Rob house 1 (1) + house 3 (3) = 4

Input:  nums = [2, 7, 9, 3, 1]
Output: 12
Explanation: Rob house 1 (2) + house 3 (9) + house 5 (1) = 12
```

Constraints
-----------
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 400
"""

from typing import List
from functools import lru_cache


class Solution:
    # Approach 1: Top-down memoization — O(n) time, O(n) space
    def rob(self, nums: List[int]) -> int:
        # dp(i) = max(rob house i + dp(i+2), skip house i = dp(i+1))
        n = len(nums)

        @lru_cache(maxsize=None)
        def dp(i: int) -> int:
            if i >= n:
                return 0
            return max(nums[i] + dp(i + 2), dp(i + 1))

        return dp(0)

    # Approach 2: Bottom-up DP — O(n) time, O(n) space
    def rob_dp(self, nums: List[int]) -> int:
        # dp[i] = max(dp[i-1], dp[i-2] + nums[i]): rob or skip current house
        n = len(nums)
        if n == 1:
            return nums[0]
        dp = [0] * n
        dp[0], dp[1] = nums[0], max(nums[0], nums[1])
        for i in range(2, n):
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
        return dp[-1]

    # Approach 3: Space-optimized — O(n) time, O(1) space
    def rob_opt(self, nums: List[int]) -> int:
        # Rolling two variables: prev2=rob two ago, prev1=best so far
        prev2, prev1 = 0, 0
        for num in nums:
            prev2, prev1 = prev1, max(prev1, prev2 + num)
        return prev1


if __name__ == "__main__":
    sol = Solution()
    assert sol.rob([1, 2, 3, 1]) == 4
    assert sol.rob([2, 7, 9, 3, 1]) == 12
    assert sol.rob([1]) == 1
    assert sol.rob_dp([1, 2, 3, 1]) == 4
    assert sol.rob_opt([1, 2, 3, 1]) == 4
    print("All tests passed.")

"""
LC 213 — House Robber II
=========================

All houses are arranged in a circle. The first and last houses are adjacent.
You cannot rob two adjacent houses. Return the maximum amount you can rob.

Examples
--------
```text
Input:  nums = [2, 3, 2]
Output: 3
Explanation: Cannot rob house 1 (2) and house 3 (2) since they are adjacent.

Input:  nums = [1, 2, 3]
Output: 3

Input:  nums = [1, 2, 3, 1]
Output: 4
```

Constraints
-----------
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 1000
"""

from typing import List


class Solution:
    # Approach 1: Two linear passes (exclude first or exclude last) — O(n) time, O(1) space
    def rob(self, nums: List[int]) -> int:
        # Circular constraint: can't rob both first and last house
        # Run linear rob on [0..n-2] and [1..n-1]; take the max
        if len(nums) == 1:
            return nums[0]

        def rob_linear(houses: List[int]) -> int:
            prev2, prev1 = 0, 0
            for num in houses:
                prev2, prev1 = prev1, max(prev1, prev2 + num)
            return prev1

        return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))


if __name__ == "__main__":
    sol = Solution()
    assert sol.rob([2, 3, 2]) == 3
    assert sol.rob([1, 2, 3]) == 3
    assert sol.rob([1, 2, 3, 1]) == 4
    assert sol.rob([1]) == 1
    print("All tests passed.")

"""
LC 343 — Integer Break
=======================

Given an integer `n`, break it into the sum of k positive integers (k >= 2),
and maximize the product of those integers. Return the maximum product.

Examples
--------
```text
Input:  n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 * 1 = 1

Input:  n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 * 3 * 4 = 36
```

Constraints
-----------
- 2 <= n <= 58
"""


class Solution:
    # Approach 1: DP — O(n^2) time, O(n) space
    def integerBreak(self, n: int) -> int:
        # dp[i] = max product from breaking i; try all splits j and (i-j)
        # Either keep (i-j) as-is or break it further: max(i-j, dp[i-j])
        dp = [0] * (n + 1)
        dp[1] = 1
        for i in range(2, n + 1):
            for j in range(1, i):
                dp[i] = max(dp[i], j * (i - j), j * dp[i - j])
        return dp[n]

    # Approach 2: Math (greedy with 3s) — O(n) time, O(1) space
    def integerBreak_math(self, n: int) -> int:
        # Greedy: break into 3s as much as possible (3s maximize product)
        # Handle remainders 2 and 4 specially
        if n == 2:
            return 1
        if n == 3:
            return 2
        product = 1
        while n > 4:
            product *= 3
            n -= 3
        return product * n


if __name__ == "__main__":
    sol = Solution()
    assert sol.integerBreak(2) == 1
    assert sol.integerBreak(10) == 36
    assert sol.integerBreak(3) == 2
    assert sol.integerBreak_math(2) == 1
    assert sol.integerBreak_math(10) == 36
    assert sol.integerBreak_math(3) == 2
    print("All tests passed.")

"""
LC 300 — Longest Increasing Subsequence
=========================================

Given an integer array `nums`, return the length of the longest strictly
increasing subsequence.

Examples
--------
```text
Input:  nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: [2, 3, 7, 101]

Input:  nums = [0, 1, 0, 3, 2, 3]
Output: 4

Input:  nums = [7, 7, 7, 7, 7, 7, 7]
Output: 1
```

Constraints
-----------
- 1 <= nums.length <= 2500
- -10^4 <= nums[i] <= 10^4
"""

from typing import List
import bisect


class Solution:
    # Approach 1: DP — O(n^2) time, O(n) space
    def lengthOfLIS(self, nums: List[int]) -> int:
        # dp[i] = LIS ending at index i; for each j < i where nums[j] < nums[i], dp[i] = max(dp[i], dp[j]+1)
        n = len(nums)
        dp = [1] * n
        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

    # Approach 2: Binary search (patience sorting) — O(n log n) time, O(n) space
    def lengthOfLIS_bs(self, nums: List[int]) -> int:
        # Patience sorting: maintain 'tails' array; binary search for insertion position
        # tails[i] = smallest tail of all LIS of length i+1
        tails = []
        for num in nums:
            pos = bisect.bisect_left(tails, num)
            if pos == len(tails):
                tails.append(num)
            else:
                tails[pos] = num
        return len(tails)


if __name__ == "__main__":
    sol = Solution()
    assert sol.lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]) == 4
    assert sol.lengthOfLIS([0, 1, 0, 3, 2, 3]) == 4
    assert sol.lengthOfLIS([7, 7, 7, 7]) == 1
    assert sol.lengthOfLIS_bs([10, 9, 2, 5, 3, 7, 101, 18]) == 4
    assert sol.lengthOfLIS_bs([7, 7, 7, 7]) == 1
    print("All tests passed.")

"""
LC 5 — Longest Palindromic Substring
======================================

Given a string `s`, return the longest palindromic substring in `s`.

Examples
--------
```text
Input:  s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Input:  s = "cbbd"
Output: "bb"
```

Constraints
-----------
- 1 <= s.length <= 1000
- s consists of only digits and English letters
"""


class Solution:
    # Approach 1: Brute force — O(n^3) time, O(1) space
    def longestPalindrome_brute(self, s: str) -> str:
        # Try all substrings; check each for palindrome property — O(n^3)
        def is_palindrome(t: str) -> bool:
            return t == t[::-1]

        best = s[0]
        for i in range(len(s)):
            for j in range(i + 1, len(s) + 1):
                if j - i > len(best) and is_palindrome(s[i:j]):
                    best = s[i:j]
        return best

    # Approach 2: Expand around center — O(n^2) time, O(1) space
    def longestPalindrome(self, s: str) -> str:
        # Expand around each center (odd and even length) to find longest palindrome
        start, end = 0, 0

        def expand(l: int, r: int) -> tuple:
            while l >= 0 and r < len(s) and s[l] == s[r]:
                l -= 1
                r += 1
            return l + 1, r - 1

        for i in range(len(s)):
            l1, r1 = expand(i, i)
            l2, r2 = expand(i, i + 1)
            if r1 - l1 > end - start:
                start, end = l1, r1
            if r2 - l2 > end - start:
                start, end = l2, r2
        return s[start:end + 1]

    # Approach 3: DP table — O(n^2) time, O(n^2) space
    def longestPalindrome_dp(self, s: str) -> str:
        # dp[i][j] = True if s[i..j] is palindrome; build from shorter to longer
        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):
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j]:
                    dp[i][j] = length == 2 or dp[i + 1][j - 1]
                    if dp[i][j] and length > max_len:
                        start, max_len = i, length
        return s[start:start + max_len]


if __name__ == "__main__":
    sol = Solution()
    assert sol.longestPalindrome("babad") in ("bab", "aba")
    assert sol.longestPalindrome("cbbd") == "bb"
    assert sol.longestPalindrome("a") == "a"
    assert sol.longestPalindrome_brute("babad") in ("bab", "aba")
    assert sol.longestPalindrome_dp("babad") in ("bab", "aba")
    print("All tests passed.")

"""
LC 152 — Maximum Product Subarray
===================================

Given an integer array `nums`, find a contiguous subarray that has the largest product,
and return the product.

Examples
--------
```text
Input:  nums = [2, 3, -2, 4]
Output: 6
Explanation: [2, 3] has the largest product 6.

Input:  nums = [-2, 0, -1]
Output: 0
Explanation: The result cannot be 2 because [-2, -1] is not a subarray.
```

Constraints
-----------
- 1 <= nums.length <= 2 * 10^4
- -10 <= nums[i] <= 10
- The product of any subarray of nums is guaranteed to fit in a 32-bit integer.
"""

from typing import List


class Solution:
    # Approach 1: Brute force — O(n^2) time, O(1) space
    def maxProduct_brute(self, nums: List[int]) -> int:
        # Try all subarrays; track running product — O(n^2)
        best = nums[0]
        for i in range(len(nums)):
            prod = 1
            for j in range(i, len(nums)):
                prod *= nums[j]
                best = max(best, prod)
        return best

    # Approach 2: Track running min and max — O(n) time, O(1) space
    def maxProduct(self, nums: List[int]) -> int:
        # Track both max and min products (negatives can flip sign)
        # At each step, new max/min comes from: num alone, num*prev_max, num*prev_min
        cur_max = cur_min = best = nums[0]
        for num in nums[1:]:
            candidates = (num, cur_max * num, cur_min * num)
            cur_max, cur_min = max(candidates), min(candidates)
            best = max(best, cur_max)
        return best


if __name__ == "__main__":
    sol = Solution()
    assert sol.maxProduct([2, 3, -2, 4]) == 6
    assert sol.maxProduct([-2, 0, -1]) == 0
    assert sol.maxProduct([-2]) == -2
    assert sol.maxProduct([0, 2]) == 2
    assert sol.maxProduct_brute([2, 3, -2, 4]) == 6
    print("All tests passed.")

"""
LC 746 — Min Cost Climbing Stairs
==================================

You are given an integer array `cost` where `cost[i]` is the cost of the i-th step.
Once you pay the cost, you can climb one or two steps.
You can either start from index 0 or index 1.
Return the minimum cost to reach the top of the floor (beyond the last index).

Examples
--------
```text
Input:  cost = [10, 15, 20]
Output: 15
Explanation: Start at index 1, pay 15, climb 2 steps to the top.

Input:  cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
```

Constraints
-----------
- 2 <= cost.length <= 1000
- 0 <= cost[i] <= 999
"""

from typing import List
from functools import lru_cache


class Solution:
    # Approach 1: Top-down memoization — O(n) time, O(n) space
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # dp(i) = cost[i] + min(dp(i+1), dp(i+2)); can start at 0 or 1
        n = len(cost)

        @lru_cache(maxsize=None)
        def dp(i: int) -> int:
            if i >= n:
                return 0
            return cost[i] + min(dp(i + 1), dp(i + 2))

        return min(dp(0), dp(1))

    # Approach 2: Bottom-up DP — O(n) time, O(n) space
    def minCostClimbingStairs_dp(self, cost: List[int]) -> int:
        # dp[i] = min cost to reach step i from step i-1 or i-2
        n = len(cost)
        dp = [0] * (n + 1)
        for i in range(2, n + 1):
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
        return dp[n]

    # Approach 3: Space-optimized — O(n) time, O(1) space
    def minCostClimbingStairs_opt(self, cost: List[int]) -> int:
        # Rolling two variables for O(1) space
        a, b = 0, 0
        for i in range(2, len(cost) + 1):
            a, b = b, min(b + cost[i - 1], a + cost[i - 2])
        return b


if __name__ == "__main__":
    sol = Solution()
    assert sol.minCostClimbingStairs([10, 15, 20]) == 15
    assert sol.minCostClimbingStairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]) == 6
    assert sol.minCostClimbingStairs_dp([10, 15, 20]) == 15
    assert sol.minCostClimbingStairs_opt([10, 15, 20]) == 15
    print("All tests passed.")

"""
LC 1137 — N-th Tribonacci Number
==================================

The Tribonacci sequence is defined as:
  T(0) = 0, T(1) = 1, T(2) = 1
  T(n) = T(n-1) + T(n-2) + T(n-3) for n >= 3

Return the value of T(n).

Examples
--------
```text
Input:  n = 4
Output: 4
Explanation: T(4) = T(3) + T(2) + T(1) = 2 + 1 + 1 = 4

Input:  n = 25
Output: 1389537
```

Constraints
-----------
- 0 <= n <= 37
"""


class Solution:
    # Approach 1: DP array — O(n) time, O(n) space
    def tribonacci(self, n: int) -> int:
        # dp[i] = dp[i-1] + dp[i-2] + dp[i-3]; base cases T(0)=0, T(1)=T(2)=1
        if n == 0:
            return 0
        if n <= 2:
            return 1
        dp = [0] * (n + 1)
        dp[1] = dp[2] = 1
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
        return dp[n]

    # Approach 2: Space-optimized — O(n) time, O(1) space
    def tribonacci_opt(self, n: int) -> int:
        # Rolling three variables: a, b, c represent T(n-2), T(n-1), T(n)
        if n == 0:
            return 0
        if n <= 2:
            return 1
        a, b, c = 0, 1, 1
        for _ in range(3, n + 1):
            a, b, c = b, c, a + b + c
        return c


if __name__ == "__main__":
    sol = Solution()
    assert sol.tribonacci(0) == 0
    assert sol.tribonacci(1) == 1
    assert sol.tribonacci(2) == 1
    assert sol.tribonacci(4) == 4
    assert sol.tribonacci(25) == 1389537
    assert sol.tribonacci_opt(4) == 4
    assert sol.tribonacci_opt(25) == 1389537
    print("All tests passed.")

"""
LC 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.

Examples
--------
```text
Input:  s = "abc"
Output: 3
Explanation: "a", "b", "c"

Input:  s = "aaa"
Output: 6
Explanation: "a", "a", "a", "aa", "aa", "aaa"
```

Constraints
-----------
- 1 <= s.length <= 1000
- s consists of lowercase English letters
"""


class Solution:
    # Approach 1: Expand around center — O(n^2) time, O(1) space
    def countSubstrings(self, s: str) -> int:
        # Expand around each center; count every valid palindrome found
        count = 0

        def expand(l: int, r: int) -> None:
            nonlocal count
            while l >= 0 and r < len(s) and s[l] == s[r]:
                count += 1
                l -= 1
                r += 1

        for i in range(len(s)):
            expand(i, i)
            expand(i, i + 1)
        return count

    # Approach 2: DP table — O(n^2) time, O(n^2) space
    def countSubstrings_dp(self, s: str) -> int:
        # dp[i][j] = True if s[i..j] is palindrome; count all True entries
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        count = 0
        for length in range(1, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j] and (length <= 2 or dp[i + 1][j - 1]):
                    dp[i][j] = True
                    count += 1
        return count


if __name__ == "__main__":
    sol = Solution()
    assert sol.countSubstrings("abc") == 3
    assert sol.countSubstrings("aaa") == 6
    assert sol.countSubstrings_dp("abc") == 3
    assert sol.countSubstrings_dp("aaa") == 6
    print("All tests passed.")

"""
LC 416 — Partition Equal Subset Sum
=====================================

Given an integer array `nums`, return true if you can partition the array into
two subsets such that the sum of the elements in both subsets is equal.

Examples
--------
```text
Input:  nums = [1, 5, 11, 5]
Output: true
Explanation: [1, 5, 5] and [11]

Input:  nums = [1, 2, 3, 5]
Output: false
```

Constraints
-----------
- 1 <= nums.length <= 200
- 1 <= nums[i] <= 100
"""

from typing import List
from functools import lru_cache


class Solution:
    # Approach 1: Top-down memoization — O(n * sum) time, O(n * sum) space
    def canPartition(self, nums: List[int]) -> bool:
        # Reduce to subset sum: can we find a subset summing to total/2?
        total = sum(nums)
        if total % 2:
            return False
        target = total // 2

        @lru_cache(maxsize=None)
        def dp(i: int, rem: int) -> bool:
            if rem == 0:
                return True
            if i == len(nums) or rem < 0:
                return False
            return dp(i + 1, rem - nums[i]) or dp(i + 1, rem)

        return dp(0, target)

    # Approach 2: Bottom-up DP (boolean set) — O(n * sum) time, O(sum) space
    def canPartition_dp(self, nums: List[int]) -> bool:
        # dp = set of reachable sums; for each num, add num to all existing sums
        total = sum(nums)
        if total % 2:
            return False
        target = total // 2
        dp = {0}
        for num in nums:
            dp |= {s + num for s in dp if s + num <= target}
        return target in dp

    # Approach 3: Bitset optimization — O(n * sum / 64) time, O(sum / 64) space
    def canPartition_bitset(self, nums: List[int]) -> bool:
        # Bitset trick: bit i set means sum i is reachable; shift and OR for each num
        total = sum(nums)
        if total % 2:
            return False
        target = total // 2
        bits = 1
        for num in nums:
            bits |= bits << num
        return bool((bits >> target) & 1)


if __name__ == "__main__":
    sol = Solution()
    assert sol.canPartition([1, 5, 11, 5]) is True
    assert sol.canPartition([1, 2, 3, 5]) is False
    assert sol.canPartition_dp([1, 5, 11, 5]) is True
    assert sol.canPartition_dp([1, 2, 3, 5]) is False
    assert sol.canPartition_bitset([1, 5, 11, 5]) is True
    assert sol.canPartition_bitset([1, 2, 3, 5]) is False
    print("All tests passed.")

"""
LC 279 — Perfect Squares
==========================

Given an integer `n`, return the least number of perfect square numbers that sum to `n`.
A perfect square is an integer that is the square of an integer (1, 4, 9, 16, ...).

Examples
--------
```text
Input:  n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4

Input:  n = 13
Output: 2
Explanation: 13 = 4 + 9
```

Constraints
-----------
- 1 <= n <= 10^4
"""

from collections import deque
import math


class Solution:
    # Approach 1: DP — O(n * sqrt(n)) time, O(n) space
    def numSquares(self, n: int) -> int:
        # dp[i] = min squares summing to i; try all perfect squares <= i
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        squares = [i * i for i in range(1, int(math.isqrt(n)) + 1)]
        for i in range(1, n + 1):
            for sq in squares:
                if sq > i:
                    break
                dp[i] = min(dp[i], dp[i - sq] + 1)
        return dp[n]

    # Approach 2: BFS (level = number of squares used) — O(n * sqrt(n)) time, O(n) space
    def numSquares_bfs(self, n: int) -> int:
        # BFS levels = number of squares used; find shortest path from n to 0
        squares = [i * i for i in range(1, int(math.isqrt(n)) + 1)]
        visited = {n}
        queue = deque([n])
        steps = 0
        while queue:
            steps += 1
            for _ in range(len(queue)):
                node = queue.popleft()
                for sq in squares:
                    nxt = node - sq
                    if nxt == 0:
                        return steps
                    if nxt > 0 and nxt not in visited:
                        visited.add(nxt)
                        queue.append(nxt)
        return steps


if __name__ == "__main__":
    sol = Solution()
    assert sol.numSquares(12) == 3
    assert sol.numSquares(13) == 2
    assert sol.numSquares(1) == 1
    assert sol.numSquares_bfs(12) == 3
    assert sol.numSquares_bfs(13) == 2
    print("All tests passed.")

"""
LC 1406 — Stone Game III
=========================

Alice and Bob take turns, with Alice going first. On each turn, a player can take
1, 2, or 3 stones from the front of the row. The player with the most stones wins.

Return "Alice" if Alice wins, "Bob" if Bob wins, or "Tie" if they end with the same score.
Both players play optimally.

Examples
--------
```text
Input:  stoneValue = [1, 2, 3, 7]
Output: "Bob"
Explanation: Alice takes 1, 2, or 3 stones; Bob always wins.

Input:  stoneValue = [1, 2, 3, -9]
Output: "Alice"

Input:  stoneValue = [1, 2, 3, 6]
Output: "Tie"
```

Constraints
-----------
- 1 <= stoneValue.length <= 5 * 10^4
- -1000 <= stoneValue[i] <= 1000
"""

from typing import List
from functools import lru_cache


class Solution:
    # Approach 1: Top-down memoization — O(n) time, O(n) space
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        # dp(i) = max score advantage current player can get from index i
        # Try taking 1, 2, or 3 stones; subtract opponent's optimal play
        n = len(stoneValue)

        @lru_cache(maxsize=None)
        def dp(i: int) -> int:
            """Returns max score advantage current player can achieve from index i."""
            if i >= n:
                return 0
            best = float('-inf')
            total = 0
            for k in range(1, 4):
                if i + k - 1 < n:
                    total += stoneValue[i + k - 1]
                    best = max(best, total - dp(i + k))
            return best

        score = dp(0)
        if score > 0:
            return "Alice"
        elif score < 0:
            return "Bob"
        return "Tie"

    # Approach 2: Bottom-up DP — O(n) time, O(n) space
    def stoneGameIII_dp(self, stoneValue: List[int]) -> str:
        # Bottom-up: dp[i] = max(sum of k stones - dp[i+k]) for k in 1..3
        n = len(stoneValue)
        dp = [float('-inf')] * (n + 1)
        dp[n] = 0
        for i in range(n - 1, -1, -1):
            total = 0
            for k in range(1, 4):
                if i + k <= n:
                    total += stoneValue[i + k - 1]
                    dp[i] = max(dp[i], total - dp[i + k])
        score = dp[0]
        if score > 0:
            return "Alice"
        elif score < 0:
            return "Bob"
        return "Tie"


if __name__ == "__main__":
    sol = Solution()
    assert sol.stoneGameIII([1, 2, 3, 7]) == "Bob"
    assert sol.stoneGameIII([1, 2, 3, -9]) == "Alice"
    assert sol.stoneGameIII([1, 2, 3, 6]) == "Tie"
    assert sol.stoneGameIII_dp([1, 2, 3, 7]) == "Bob"
    assert sol.stoneGameIII_dp([1, 2, 3, 6]) == "Tie"
    print("All tests passed.")

"""
LC 139 — Word Break
====================

Given a string `s` and a dictionary of strings `wordDict`, return true if `s`
can be segmented into a space-separated sequence of one or more dictionary words.
The same word in the dictionary may be reused multiple times.

Examples
--------
```text
Input:  s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: "leetcode" can be segmented as "leet code".

Input:  s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: "applepenapple" can be segmented as "apple pen apple".

Input:  s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
```

Constraints
-----------
- 1 <= s.length <= 300
- 1 <= wordDict.length <= 1000
- 1 <= wordDict[i].length <= 20
- s and wordDict[i] consist of only lowercase English letters
- All strings in wordDict are unique
"""

from typing import List
from functools import lru_cache


class Solution:
    # Approach 1: Top-down memoization — O(n^2 * m) time, O(n) space
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # dp(i): can s[i:] be segmented? Try all words starting at i
        word_set = set(wordDict)

        @lru_cache(maxsize=None)
        def dp(i: int) -> bool:
            if i == len(s):
                return True
            return any(s[i:j] in word_set and dp(j) for j in range(i + 1, len(s) + 1))

        return dp(0)

    # Approach 2: Bottom-up DP — O(n^2 * m) time, O(n) space
    def wordBreak_dp(self, s: str, wordDict: List[str]) -> bool:
        # dp[i] = True if s[:i] can be segmented; check all j < i where dp[j] and s[j:i] in dict
        word_set = set(wordDict)
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True
        for i in range(1, n + 1):
            for j in range(i):
                if dp[j] and s[j:i] in word_set:
                    dp[i] = True
                    break
        return dp[n]


if __name__ == "__main__":
    sol = Solution()
    assert sol.wordBreak("leetcode", ["leet", "code"]) is True
    assert sol.wordBreak("applepenapple", ["apple", "pen"]) is True
    assert sol.wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"]) is False
    assert sol.wordBreak_dp("leetcode", ["leet", "code"]) is True
    assert sol.wordBreak_dp("catsandog", ["cats", "dog", "sand", "and", "cat"]) is False
    print("All tests passed.")