"""
# Check Palindrome (Recursive)

Given a string `s`, return `True` if it reads the same forwards and backwards,
`False` otherwise. Solved with recursion — no loops, no reversal.

## Examples
```text
Input:  s = "racecar"
Output: True

Input:  s = "abc"
Output: False
```

## Constraints
- Compare the outer characters, then recurse on the middle substring.
- Empty string and single characters are palindromes.
"""
class Solution:
    def isPalindrome(self, s: str) -> bool:
        # Base case: empty string or single char is always a palindrome
        if len(s) <= 1:
            return True
        # Recursive case: first and last chars must match, then check middle
        if s[0] != s[-1]:
            return False
        return self.isPalindrome(s[1:-1])


if __name__ == "__main__":
    sol = Solution()
    assert sol.isPalindrome("racecar") is True
    assert sol.isPalindrome("abba") is True
    assert sol.isPalindrome("a") is True
    assert sol.isPalindrome("") is True
    assert sol.isPalindrome("abc") is False
    assert sol.isPalindrome("abcba") is True
    print("All tests passed.")

"""
Check if Any Subsequence with Sum K Exists

Problem: Return True if any subsequence of nums sums to k, else False.

Examples:
    nums = [1, 2, 3, 4], k = 6 -> True  ([2,4] or [1,2,3])
    nums = [1, 2, 3],    k = 7 -> False

Constraints:
    1 <= nums.length <= 20
    0 <= nums[i] <= 100

Approach: Recursion with early termination O(2^n) worst case.
    Same include/exclude tree as count variant, but short-circuit on first hit.
"""

from typing import List


class Solution:
    def hasSubsequenceSum(self, nums: List[int], k: int) -> bool:
        def recurse(idx: int, remaining: int) -> bool:
            # Base case: found a valid subsequence
            if remaining == 0:
                return True
            # Base case: exhausted array without hitting sum
            if idx == len(nums):
                return False
            # Include current element (only if it doesn't overshoot)
            if nums[idx] <= remaining and recurse(idx + 1, remaining - nums[idx]):
                return True  # early termination
            # Exclude current element
            return recurse(idx + 1, remaining)

        return recurse(0, k)


if __name__ == '__main__':
    sol = Solution()
    assert sol.hasSubsequenceSum([1, 2, 3, 4], 6) is True
    assert sol.hasSubsequenceSum([1, 2, 3], 7) is False
    assert sol.hasSubsequenceSum([1, 2, 1], 2) is True
    assert sol.hasSubsequenceSum([5], 5) is True
    assert sol.hasSubsequenceSum([5], 3) is False
    print("All tests passed.")

"""
LC 1922 - Count Good Numbers

Problem: A digit string is "good" if:
    - Even indices (0,2,4,...) contain even digits: {0,2,4,6,8} -> 5 choices
    - Odd  indices (1,3,5,...) contain prime digits: {2,3,5,7}  -> 4 choices
Count good strings of length n, return result mod 10^9+7.

Examples:
    n = 1  -> 5
    n = 4  -> 400
    n = 50 -> 564908303

Constraints:
    1 <= n <= 10^15
    Return answer mod 10^9 + 7
"""

import math

MOD = 10**9 + 7


class Solution:
    def countGoodNumbers(self, n: int) -> int:
        # even_count = ceil(n/2) positions with 5 choices each
        # odd_count  = floor(n/2) positions with 4 choices each
        # Use fast modular exponentiation (pow built-in) for O(log n)
        even_count = math.ceil(n / 2)
        odd_count = n // 2
        return (pow(5, even_count, MOD) * pow(4, odd_count, MOD)) % MOD


if __name__ == '__main__':
    sol = Solution()
    assert sol.countGoodNumbers(1) == 5
    assert sol.countGoodNumbers(4) == 400
    assert sol.countGoodNumbers(50) == 564908303
    print("All tests passed.")

"""
Count Subsequences with Sum K

Problem: Count all subsequences of an array whose elements sum to k.

Examples:
    nums = [1, 2, 1], k = 2 -> 2  (subsequences: [1,1] and [2])
    nums = [1, 1, 1], k = 2 -> 3

Constraints:
    1 <= nums.length <= 20
    0 <= nums[i] <= 100
    0 <= k <= 1000
"""

from typing import List


class Solution:
    # Approach 1: Recursion with memoization O(n * k)
    def countSubsequences(self, nums: List[int], k: int) -> int:
        from functools import lru_cache

        n = len(nums)

        @lru_cache(maxsize=None)
        def dp(idx: int, remaining: int) -> int:
            # Base case: processed all elements
            if idx == n:
                return 1 if remaining == 0 else 0
            # Exclude current element
            count = dp(idx + 1, remaining)
            # Include current element only if it doesn't exceed remaining sum
            if nums[idx] <= remaining:
                count += dp(idx + 1, remaining - nums[idx])
            return count

        return dp(0, k)

    # Approach 2: Backtracking O(2^n) — explicit include/exclude tree
    def countSubsequences_backtrack(self, nums: List[int], k: int) -> int:
        count = [0]

        def backtrack(idx: int, current_sum: int) -> None:
            # Base case: reached end, check if sum matches
            if idx == len(nums):
                if current_sum == k:
                    count[0] += 1
                return
            # Include nums[idx]
            backtrack(idx + 1, current_sum + nums[idx])
            # Exclude nums[idx]
            backtrack(idx + 1, current_sum)

        backtrack(0, 0)
        return count[0]


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

"""
# Fibonacci Variants

1. Compute the nth Fibonacci number (0-indexed: fib(0)=0, fib(1)=1).
2. Count the number of ways to climb n stairs taking 1 or 2 steps at a time.

## Examples
```text
Input:  fib(10)
Output: 55

Input:  climbStairs(5)
Output: 8
```

## Constraints
- fib(0) = 0, fib(1) = 1; fib(n) = fib(n-1) + fib(n-2).
- climbStairs(n) = climbStairs(n-1) + climbStairs(n-2).
- For large n, prefer the memoized or iterative approach to avoid recursion limits.
"""
class Solution:
    def fib_naive(self, n: int) -> int:
        # Approach 1: Naive recursion O(2^n) — recomputes same subproblems repeatedly
        if n <= 1:
            return n
        return self.fib_naive(n - 1) + self.fib_naive(n - 2)

    def fib(self, n: int) -> int:
        # Approach 2: Memoized recursion O(n) — cache results to avoid recomputation
        memo = {}

        def dp(n):
            if n <= 1:
                return n
            if n in memo:
                return memo[n]
            memo[n] = dp(n - 1) + dp(n - 2)
            return memo[n]

        return dp(n)

    def fib_iterative(self, n: int) -> int:
        # Approach 3: Iterative O(n) time, O(1) space — no recursion overhead
        if n <= 1:
            return n
        a, b = 0, 1
        for _ in range(2, n + 1):
            a, b = b, a + b
        return b

    def climbStairs(self, n: int) -> int:
        # Count ways to climb n stairs (1 or 2 steps at a time) — same recurrence as fib
        # climbStairs(n) = climbStairs(n-1) + climbStairs(n-2)
        if n <= 2:
            return n
        a, b = 1, 2
        for _ in range(3, n + 1):
            a, b = b, a + b
        return b


if __name__ == "__main__":
    sol = Solution()
    assert sol.fib(10) == 55
    assert sol.fib_naive(10) == 55
    assert sol.fib_iterative(10) == 55
    assert sol.climbStairs(5) == 8
    assert sol.climbStairs(1) == 1
    assert sol.climbStairs(2) == 2
    print("All tests passed.")

"""
# 733: Flood Fill (Recursive)

Given a 2D `image` grid, a starting cell `(sr, sc)`, and a new `color`, perform
a flood fill: change the starting cell and all 4-directionally connected cells
of the same original color to `color`.

## Examples
```text
Input:  image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
```

## Constraints
- Connectivity is 4-directional (up, down, left, right).
- If the starting cell already has the target color, return the image unchanged.
"""
from typing import List


class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        # DFS recursive O(m*n).
        # Capture the original color at the starting cell before any changes.
        # Base case: out of bounds, different original color, or already filled.
        original = image[sr][sc]
        if original == color:  # already the target color — avoid infinite loop
            return image

        def dfs(r, c):
            if r < 0 or r >= len(image) or c < 0 or c >= len(image[0]):
                return  # out of bounds
            if image[r][c] != original:
                return  # different color — stop spreading
            image[r][c] = color  # fill current cell
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        dfs(sr, sc)
        return image


if __name__ == "__main__":
    sol = Solution()
    img = [[1, 1, 1], [1, 1, 0], [1, 0, 1]]
    result = sol.floodFill(img, 1, 1, 2)
    assert result == [[2, 2, 2], [2, 2, 0], [2, 0, 1]]

    # Already target color — no change
    img2 = [[0, 0, 0], [0, 0, 0]]
    assert sol.floodFill(img2, 0, 0, 0) == [[0, 0, 0], [0, 0, 0]]

    # Single cell
    assert sol.floodFill([[1]], 0, 0, 5) == [[5]]
    print("All tests passed.")

"""
# 22: Generate All Balanced Parentheses

Given `n` pairs of parentheses, generate all combinations of well-formed
(balanced) parentheses strings.

## Examples
```text
Input:  n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Input:  n = 1
Output: ["()"]
```

## Constraints
- 1 <= n <= 8 (typical).
- The number of valid combinations equals the nth Catalan number.
"""
from typing import List


class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        # Recursion with open/close count tracking.
        # Place '(' if open < n (still have opening brackets to use).
        # Place ')' if close < open (can only close what's been opened).
        result = []

        def recurse(current, open_count, close_count):
            if len(current) == 2 * n:  # base case: used all n pairs
                result.append(current)
                return
            if open_count < n:
                recurse(current + "(", open_count + 1, close_count)
            if close_count < open_count:
                recurse(current + ")", open_count, close_count + 1)

        recurse("", 0, 0)
        return result


if __name__ == "__main__":
    sol = Solution()
    r = sol.generateParenthesis(3)
    assert len(r) == 5
    assert "(((())))" not in r  # invalid
    assert "((()))" in r
    assert "(()())" in r
    assert len(sol.generateParenthesis(1)) == 1
    assert sol.generateParenthesis(1) == ["()"]
    print("All tests passed.")

"""
Generate Binary Strings Without Consecutive 1s

Problem: Generate all binary strings of length n that do not contain consecutive 1s.

Examples:
    n = 3 -> ["000", "001", "010", "100", "101"]
    n = 1 -> ["0", "1"]

Constraints:
    1 <= n <= 20

Approach: Backtracking O(2^n) — at each position decide '0' or '1',
    but if last character placed was '1', next must be '0'.
"""

from typing import List


class Solution:
    def generateStrings(self, n: int) -> List[str]:
        result = []

        def backtrack(current: str) -> None:
            # Base case: string has reached desired length
            if len(current) == n:
                result.append(current)
                return
            # Always allowed to place '0'
            backtrack(current + '0')
            # Place '1' only if last character is not '1'
            if not current or current[-1] != '1':
                backtrack(current + '1')

        backtrack("")
        return sorted(result)  # return in lexicographic order


if __name__ == '__main__':
    sol = Solution()
    assert sol.generateStrings(3) == ["000", "001", "010", "100", "101"]
    assert sol.generateStrings(1) == ["0", "1"]
    # Verify no consecutive 1s in any result
    for s in sol.generateStrings(5):
        assert "11" not in s
    print("All tests passed.")

"""
# Josephus Problem

Given `n` people standing in a circle (0-indexed), every `k`th person is
eliminated until only one remains. Return the 0-indexed position of the survivor.

## Examples
```text
Input:  n = 7, k = 3
Output: 3

Input:  n = 5, k = 2
Output: 2
```

## Constraints
- n >= 1, k >= 1.
- Recurrence: J(1, k) = 0; J(n, k) = (J(n-1, k) + k) % n.
"""
from typing import List


class Solution:
    def josephus_simulation(self, n: int, k: int) -> int:
        # Approach 1: Simulation O(n*k) — maintain a list, remove every kth person
        people = list(range(n))
        idx = 0
        while len(people) > 1:
            idx = (idx + k - 1) % len(people)  # move k-1 steps forward
            people.pop(idx)
            if idx == len(people):  # wrap around after removal
                idx = 0
        return people[0]

    def josephus(self, n: int, k: int) -> int:
        # Approach 2: Recursive formula O(n)
        # J(1, k) = 0  (only one person, 0-indexed position)
        # J(n, k) = (J(n-1, k) + k) % n
        # After eliminating the kth person, the circle shrinks to n-1 people.
        # The result for n-1 people is shifted by k positions in the original indexing.
        if n == 1:
            return 0
        return (self.josephus(n - 1, k) + k) % n


if __name__ == "__main__":
    sol = Solution()
    # n=7, k=3 -> 3 (0-indexed)
    assert sol.josephus(7, 3) == 3
    assert sol.josephus_simulation(7, 3) == 3
    # n=1 -> only one person, position 0
    assert sol.josephus(1, 1) == 0
    # n=5, k=2 -> 2
    assert sol.josephus(5, 2) == 2
    assert sol.josephus_simulation(5, 2) == 2
    print("All tests passed.")

from typing import List


class Solution:
    """
    **LC 779: K-th Symbol in Grammar**

    We build a table of `n` rows (1-indexed). We start by writing `0` in the 1st row.
    In every subsequent row, we look at the previous row and replace each occurrence of:
    * `0` with `01`
    * `1` with `10`

    Given two integers `n` and `k`, return the `k`-th (1-indexed) symbol in the `n`-th row.

    ```text
    Row 1: 0
    Row 2: 01
    Row 3: 0110
    Row 4: 01101001
    ```

    Example 1:
    ```text
    Input:  n = 1, k = 1
    Output: 0
    ```

    Example 2:
    ```text
    Input:  n = 2, k = 1
    Output: 0
    ```

    Example 3:
    ```text
    Input:  n = 2, k = 2
    Output: 1
    ```

    **Constraints:**
    * `1 <= n <= 30`
    * `1 <= k <= 2^(n - 1)`
    """

    def kthGrammar(self, n: int, k: int) -> int:
        # Each row is double the previous; k-th symbol in row n mirrors row n-1
        # If k <= mid: same as parent symbol; if k > mid: flip the parent symbol (XOR 1)
        # your code here
        def solve(n, k):
            if n == 1 and k == 1:
                return 0
            mid = 2 ** (n - 2)

            if k <= mid:
                return solve(n - 1, k)
            else:
                return solve(n - 1, k - mid) ^ 1
        
        return solve(n, k)
        pass


if __name__ == "__main__":
    sol = Solution()

    # Example 1: expected 0
    print(sol.kthGrammar(1, 1))

    # Example 2: expected 0
    print(sol.kthGrammar(2, 1))

    # Example 3: expected 1
    print(sol.kthGrammar(2, 2))

from typing import List


class Solution:
    """
    **LC 784: Letter Case Permutation**

    Given a string `s`, you can transform every letter individually to be lowercase
    or uppercase to create another string.

    Return a list of **all possible strings** we could create. Return the output in any order.
    Digits remain unchanged.

    Example 1:
    ```text
    Input:  s = "a1b2"
    Output: ["a1b2", "a1B2", "A1b2", "A1B2"]
    ```

    Example 2:
    ```text
    Input:  s = "3z4"
    Output: ["3z4", "3Z4"]
    ```

    **Constraints:**
    * `1 <= s.length <= 12`
    * `s` consists of lowercase English letters, uppercase English letters, and digits
    """

    def letterCasePermutation(self, s: str) -> List[str]:
        # Approach: DFS/backtracking through each character
        # 1. If digit, move to next character unchanged
        # 2. If letter, branch: recurse with lowercase version AND uppercase version
        # 3. When index reaches end of string, add current path to results
        # your code here
        pass


if __name__ == "__main__":
    sol = Solution()

    # Example 1: expected ["a1b2", "a1B2", "A1b2", "A1B2"]
    print(sol.letterCasePermutation("a1b2"))

    # Example 2: expected ["3z4", "3Z4"]
    print(sol.letterCasePermutation("3z4"))

"""
# Power Set (Recursive)

Given an array `nums`, return all possible subsets (the power set). The
solution set must not contain duplicate subsets.

## Examples
```text
Input:  nums = [1,2,3]
Output: [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
```

## Constraints
- Uses the include/exclude decision pattern at each index.
- Produces 2^n subsets; input is assumed to contain distinct elements.
"""
from typing import List


class Solution:
    def powerSet(self, nums: List[int]) -> List[List[int]]:
        # Include/exclude pattern: at each index, branch into two choices.
        # Total subsets = 2^n (each element is either in or out).
        result = []

        def recurse(idx, current):
            if idx == len(nums):
                result.append(current[:])  # base case: all elements decided
                return
            # Exclude nums[idx]
            recurse(idx + 1, current)
            # Include nums[idx]
            current.append(nums[idx])
            recurse(idx + 1, current)
            current.pop()  # backtrack

        recurse(0, [])
        return result


if __name__ == "__main__":
    sol = Solution()
    result = sol.powerSet([1, 2, 3])
    assert len(result) == 8  # 2^3 subsets
    # Check empty set and full set are present
    assert [] in result
    assert [1, 2, 3] in result
    # Single element
    assert len(sol.powerSet([1])) == 2
    # Empty input
    assert sol.powerSet([]) == [[]]
    print("All tests passed.")

"""
# Print All Permutations

Given an array of distinct integers `nums`, return all possible permutations.

## Examples
```text
Input:  nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
```

## Constraints
- Elements are distinct; the result contains n! permutations.
"""
from typing import List


class Solution:
    def permute_swap(self, nums: List[int]) -> List[List[int]]:
        # Approach 1: Swap-based O(n!)
        # Fix one element at position `start` by swapping it with each element,
        # then recurse on the remaining suffix.
        result = []

        def recurse(start):
            if start == len(nums):
                result.append(nums[:])
                return
            for i in range(start, len(nums)):
                nums[start], nums[i] = nums[i], nums[start]  # fix nums[i] at start
                recurse(start + 1)
                nums[start], nums[i] = nums[i], nums[start]  # backtrack

        recurse(0)
        return result

    def permute(self, nums: List[int]) -> List[List[int]]:
        # Approach 2: Pick from remaining O(n!)
        # At each step, pick any unused element for the current position.
        result = []

        def recurse(current, remaining):
            if not remaining:
                result.append(current)
                return
            for i in range(len(remaining)):
                recurse(current + [remaining[i]], remaining[:i] + remaining[i+1:])

        recurse([], nums)
        return result


if __name__ == "__main__":
    sol = Solution()
    r1 = sol.permute_swap([1, 2, 3])
    r2 = sol.permute([1, 2, 3])
    assert len(r1) == 6
    assert len(r2) == 6
    assert sorted(r1) == sorted(r2)
    # Single element
    assert sol.permute([1]) == [[1]]
    print("All tests passed.")

"""
LC 8 Variant - String to Integer (atoi) - Recursive Implementation

Problem: Implement atoi which converts a string to a 32-bit signed integer recursively.
Steps: strip leading whitespace, read optional sign, read digits until non-digit.

Examples:
    s = "   -42"       -> -42
    s = "4193 with words" -> 4193
    s = "words and 987"  -> 0

Constraints:
    0 <= s.length <= 200
    Clamp result to [-2^31, 2^31 - 1]
"""

INT_MIN, INT_MAX = -(2**31), 2**31 - 1


class Solution:
    def myAtoi(self, s: str) -> int:
        # Strip leading whitespace upfront, then delegate to recursive helper
        s = s.lstrip()
        if not s:
            return 0

        sign = 1
        start = 0
        if s[0] in ('+', '-'):
            sign = -1 if s[0] == '-' else 1
            start = 1

        def recurse(idx: int, current: int) -> int:
            # Base case: end of string or non-digit character
            if idx == len(s) or not s[idx].isdigit():
                return current
            # Recursive case: shift current left and add new digit
            return recurse(idx + 1, current * 10 + int(s[idx]))

        result = sign * recurse(start, 0)
        return max(INT_MIN, min(INT_MAX, result))  # clamp to 32-bit range


if __name__ == '__main__':
    sol = Solution()
    assert sol.myAtoi("   -42") == -42
    assert sol.myAtoi("4193 with words") == 4193
    assert sol.myAtoi("words and 987") == 0
    assert sol.myAtoi("") == 0
    assert sol.myAtoi("-91283472332") == INT_MIN
    assert sol.myAtoi("91283472332") == INT_MAX
    print("All tests passed.")

"""
Reverse Stack Using Recursion

Problem: Reverse a stack using only recursion. No extra data structures allowed.

Examples:
    [1, 2, 3] (top=3) -> [3, 2, 1] (top=1)
    [1]               -> [1]

Constraints:
    Only recursion allowed (no auxiliary stack/queue/list).

Approach: O(n^2) time, O(n) space (call stack)
    - Pop top element
    - Recursively reverse the remaining stack
    - Insert the popped element at the bottom
"""

from typing import List


class Solution:
    def reverseStack(self, stack: List[int]) -> List[int]:
        # Base case: empty or single element — already reversed
        if len(stack) <= 1:
            return stack
        # Pop top, reverse the rest, then insert top at the bottom
        top = stack.pop()
        self.reverseStack(stack)
        self._insertAtBottom(stack, top)
        return stack

    def _insertAtBottom(self, stack: List[int], val: int) -> None:
        # Base case: empty stack — just push the value
        if not stack:
            stack.append(val)
            return
        # Hold current top, recurse to reach bottom, then restore top
        top = stack.pop()
        self._insertAtBottom(stack, val)
        stack.append(top)


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

"""
Sort Stack Using Recursion

Problem: Sort a stack in ascending order (smallest on top) using only recursion.
No extra data structures allowed — only the call stack.

Examples:
    [3, 1, 2] (top=3) -> [1, 2, 3] (top=1)
    [5, 1, 4, 2, 3]   -> [1, 2, 3, 4, 5]

Constraints:
    Stack elements are integers.
    Only recursion allowed (no auxiliary stack/queue/list).

Approach: O(n^2) time, O(n) space (call stack)
    - Pop top element
    - Recursively sort the remaining stack
    - Insert the popped element into its correct sorted position
"""

from typing import List


class Solution:
    def sortStack(self, stack: List[int]) -> List[int]:
        # Base case: empty stack is already sorted
        if not stack:
            return stack
        # Pop top, sort the rest, then insert top in correct position
        top = stack.pop()
        self.sortStack(stack)
        self._insertSorted(stack, top)
        return stack

    def _insertSorted(self, stack: List[int], val: int) -> None:
        # Base case: empty stack or val is smaller than current top -> push
        if not stack or stack[-1] <= val:
            stack.append(val)
            return
        # Current top is greater than val; pop it, recurse, then restore
        top = stack.pop()
        self._insertSorted(stack, val)
        stack.append(top)


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

"""
# String to Integer (Recursive)

Convert a string of digit characters to its integer value without using
`int()`, `atoi`, or any built-in conversion. Solved with pure recursion.

## Examples
```text
Input:  s = "1234"
Output: 1234

Input:  s = "007"
Output: 7
```

## Constraints
- Input consists of digit characters only.
- Negative numbers and non-digit characters are not handled.
"""
class Solution:
    def strToInt(self, s: str) -> int:
        # Recursive approach: process one digit at a time from left to right.
        # strToInt(s[0:n]) = strToInt(s[0:n-1]) * 10 + digit_value(s[n-1])
        # Base case: single character -> return its digit value
        if len(s) == 0:
            return 0
        if len(s) == 1:
            return ord(s[0]) - ord('0')  # convert char to digit without int()
        # Recurse on all but last char, then append last digit
        return self.strToInt(s[:-1]) * 10 + (ord(s[-1]) - ord('0'))


if __name__ == "__main__":
    sol = Solution()
    assert sol.strToInt("1234") == 1234
    assert sol.strToInt("0") == 0
    assert sol.strToInt("9") == 9
    assert sol.strToInt("100") == 100
    assert sol.strToInt("999") == 999
    print("All tests passed.")

from typing import List


class Solution:
    """
    **LC 1863: Sum of All Subset XOR Totals**

    The **XOR total** of an array is defined as the bitwise XOR of all its elements,
    or `0` if the array is empty.
    * e.g. the XOR total of `[2, 5, 6]` is `2 XOR 5 XOR 6 = 1`

    Given an array `nums`, return the **sum of all XOR totals** for every subset of `nums`.

    Note: subsets with the same elements but derived independently are counted separately.

    Example 1:
    ```text
    Input:  nums = [1, 3]
    Output: 6
    Explanation: subsets → [], [1], [3], [1,3]
                 XOR totals → 0, 1, 3, 2  →  sum = 6
    ```

    Example 2:
    ```text
    Input:  nums = [5, 1, 6]
    Output: 28
    Explanation: subsets → [], [5], [1], [6], [5,1], [5,6], [1,6], [5,1,6]
                 XOR totals → 0, 5, 1, 6, 4, 3, 7, 2  →  sum = 28
    ```

    Example 3:
    ```text
    Input:  nums = [3, 4, 5, 6, 7, 8]
    Output: 480
    ```

    **Constraints:**
    * `1 <= nums.length <= 12`
    * `1 <= nums[i] <= 20`
    """

    def subsetXORSum(self, nums: List[int]) -> int:
        # Approach: backtracking over all subsets
        # 1. At each index, branch: include nums[i] in current XOR or skip it
        # 2. At leaf (index == len(nums)), add current XOR value to total sum
        # 3. Math shortcut: answer = OR of all nums, shifted left by (n-1)
        # your code here
        pass


if __name__ == "__main__":
    sol = Solution()

    # Example 1: expected 6
    print(sol.subsetXORSum([1, 3]))

    # Example 2: expected 28
    print(sol.subsetXORSum([5, 1, 6]))

    # Example 3: expected 480
    print(sol.subsetXORSum([3, 4, 5, 6, 7, 8]))

"""
# Tower of Hanoi

Transfer `n` disks from the `src` peg to the `dest` peg using `aux` as a helper.
Move one disk at a time and never place a larger disk on a smaller one. Return
the list of moves as strings like `"A->C"`.

## Examples
```text
Input:  n = 2, src = "A", dest = "C", aux = "B"
Output: ["A->B","A->C","B->C"]
```

## Constraints
- n >= 1.
- The minimum number of moves is 2^n - 1.
"""
from typing import List


class Solution:
    def towerOfHanoi(self, n: int, src: str, dest: str, aux: str) -> List[str]:
        # Recursive approach: T(n) = 2*T(n-1) + 1 = 2^n - 1 total moves
        # Step 1: move n-1 disks from src to aux (using dest as helper)
        # Step 2: move the nth (largest) disk from src to dest
        # Step 3: move n-1 disks from aux to dest (using src as helper)
        moves = []

        def hanoi(n, src, dest, aux):
            if n == 1:
                moves.append(f"{src}->{dest}")
                return
            hanoi(n - 1, src, aux, dest)   # move n-1 disks out of the way
            moves.append(f"{src}->{dest}")  # move largest disk
            hanoi(n - 1, aux, dest, src)   # move n-1 disks to destination

        hanoi(n, src, dest, aux)
        return moves


if __name__ == "__main__":
    sol = Solution()
    # n=2: A->B, A->C, B->C
    assert sol.towerOfHanoi(2, "A", "C", "B") == ["A->B", "A->C", "B->C"]
    # n=1: single move
    assert sol.towerOfHanoi(1, "A", "C", "B") == ["A->C"]
    # n=3: 7 moves
    result = sol.towerOfHanoi(3, "A", "C", "B")
    assert len(result) == 7  # 2^3 - 1
    print("All tests passed.")

"""
# 139: Word Break (Recursive)

Given a string `s` and a list of words `wordDict`, return `True` if `s` can be
segmented into a space-separated sequence of one or more dictionary words.

## Examples
```text
Input:  s = "leetcode", wordDict = ["leet","code"]
Output: True

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

## Constraints
- Dictionary words may be reused any number of times.
- Solved with recursion plus memoization on the start index.
"""
from typing import List


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # Recursive with memoization O(n^2).
        # Try every prefix of s; if prefix is in dict, recurse on the suffix.
        # Memoize results for each starting index to avoid recomputation.
        word_set = set(wordDict)
        memo = {}

        def dp(start):
            if start == len(s):  # consumed entire string — success
                return True
            if start in memo:
                return memo[start]
            for end in range(start + 1, len(s) + 1):
                if s[start:end] in word_set and dp(end):
                    memo[start] = True
                    return True
            memo[start] = False
            return False

        return dp(0)


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("a", ["a"]) is True
    print("All tests passed.")