Input: s = "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]

class Solution:
    def storeFirstOptions(self, s: str, startPos: int, firstOptions: List[str]) -> int:
        if s[startPos] != '{':
            firstOptions.append(s[startPos])
        else:
            startPos += 1
            while s[startPos] != '}':
                if s[startPos].islower():
                    firstOptions.append(s[startPos])
                startPos += 1
            firstOptions.sort()
        return startPos + 1

    def findAllWords(self, s: str, startPos: int) -> List[str]:
        if startPos == len(s):
            return [""]
        
        firstOptions = []
        remStringStartPos = self.storeFirstOptions(s, startPos, firstOptions)
        wordsWithRemString = self.findAllWords(s, remStringStartPos)
        
        expandedWords = []
        for c in firstOptions:
            for word in wordsWithRemString:
                expandedWords.append(c + word)
        return expandedWords

    def expand(self, s: str) -> List[str]:
        return self.findAllWords(s, 0)

Input: prices = ["0.700","2.800","4.900"], target = 8
Output: "1.000"

import math

def minimizeRoundingError(prices, target):
    floors = [math.floor(float(p)) for p in prices]
    ceils = [math.ceil(float(p)) for p in prices]
    total_floor = sum(floors)
    
    difference = target - total_floor
    if difference < 0 or difference > len(prices):
        return "-1"
    
    rounding_errors = [(ceil - floor, float(p) - floor) for p, floor, ceil in zip(prices, floors, ceils)]
    rounding_errors.sort(key=lambda x: x[1])
    
    rounding_error_sum = sum(floor - float(p) for floor, p in zip(floors, prices))
    
    for i in range(difference):
        rounding_error_sum += 1
    
    for i in range(difference):
        rounding_error_sum += rounding_errors[i][1]
    
    return "{:.3f}".format(rounding_error_sum)

Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

class Solution:
    def numBusesToDestination(self, routes, source, target):
        if source == target:
            return 0
        
        from collections import defaultdict, deque
        
        adjList = defaultdict(list)
        for route, stops in enumerate(routes):
            for stop in stops:
                adjList[stop].append(route)
        
        q = deque()
        vis = set()
        for route in adjList[source]:
            q.append(route)
            vis.add(route)
        
        busCount = 1
        while q:
            for _ in range(len(q)):
                route = q.popleft()
                for stop in routes[route]:
                    if stop == target:
                        return busCount
                    for nextRoute in adjList[stop]:
                        if nextRoute not in vis:
                            vis.add(nextRoute)
                            q.append(nextRoute)
            busCount += 1
        return -1

Input: s = "abcd"
Output: 0
Explanation: There is no repeating substring.

class Solution:
    def search(self, L, n, S):
        seen = set()
        for start in range(n - L + 1):
            tmp = S[start:start + L]
            if tmp in seen:
                return start
            seen.add(tmp)
        return -1

    def longestRepeatingSubstring(self, S):
        n = len(S)
        left, right = 1, n
        while left <= right:
            L = left + (right - left) // 2
            if self.search(L, n, S) != -1:
                left = L + 1
            else:
                right = L - 1
        return left - 1

Input: nums = [12,5,7,23]
Output: true

import math
from functools import reduce

def isGoodArray(nums):
    return reduce(math.gcd, nums) == 1

Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true] 
Explanation: If you give all extraCandies to:
- Kid 1, they will have 2 + 3 = 5 candies, which is the greatest among the kids.
- Kid 2, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
- Kid 3, they will have 5 + 3 = 8 candies, which is the greatest among the kids.
- Kid 4, they will have 1 + 3 = 4 candies, which is not the greatest among the kids.
- Kid 5, they will have 3 + 3 = 6 candies, which is the greatest among the kids.

class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
        maxCandies = max(candies)
        return [candy + extraCandies >= maxCandies for candy in candies]

Input: nums = [1,4,2,5,3]
Output: 11
Explanation: There are 11 valid subarrays: [1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3].

class Solution:
    def validSubarrays(self, nums: List[int]) -> int:
        ans = 0
        st = []
        
        for i in range(len(nums)):
            while st and nums[i] < nums[st[-1]]:
                ans += (i - st.pop())
            st.append(i)
        
        while st:
            ans += (len(nums) - st.pop())
        
        return ans

Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: The cell (1, 1) is as far as possible from all the land with distance 2.

from collections import deque

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        visited = [row[:] for row in grid]
        q = deque()
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    q.append((i, j))
        
        distance = -1
        while q:
            qSize = len(q)
            for _ in range(qSize):
                landCell = q.popleft()
                for dir in directions:
                    x, y = landCell[0] + dir[0], landCell[1] + dir[1]
                    if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and visited[x][y] == 0:
                        visited[x][y] = 1
                        q.append((x, y))
            distance += 1
        
        return -1 if distance == 0 else distance

Input: s = "0.(52)", t = "0.5(25)"
Output: true
Explanation: Because "0.(52)" represents 0.52525252..., and "0.5(25)" represents 0.52525252525..... , the strings represent the same number.

from math import gcd

class Fraction:
    def __init__(self, n, d):
        g = gcd(n, d)
        self.n = n // g
        self.d = d // g

    def iadd(self, other):
        numerator = self.n * other.d + self.d * other.n
        denominator = self.d * other.d
        g = gcd(numerator, denominator)
        self.n = numerator // g
        self.d = denominator // g

class Solution:
    def isRationalEqual(self, S: str, T: str) -> bool:
        f1 = self.convert(S)
        f2 = self.convert(T)
        return f1.n == f2.n and f1.d == f2.d

    def convert(self, S: str) -> Fraction:
        state = 0
        ans = Fraction(0, 1)
        decimal_size = 0

        for part in S.split('.'):
            state += 1
            if not part:
                continue
            x = int(part)
            sz = len(part)

            if state == 1:
                ans.iadd(Fraction(x, 1))
            elif state == 2:
                ans.iadd(Fraction(x, 10 ** sz))
                decimal_size = sz
            else:
                denom = 10 ** decimal_size
                denom *= 10 ** sz - 1
                ans.iadd(Fraction(x, denom))
        return ans

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

class Solution:
    def countElements(self, arr: List[int]) -> int:
        def integerInArray(arr, target):
            for x in arr:
                if x == target:
                    return True
            return False
        
        count = 0
        for x in arr:
            if integerInArray(arr, x + 1):
                count += 1
        return count

Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def widthOfBinaryTree(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        max_width = 0
        queue = deque([(root, 0)])
        
        while queue:
            level_length = len(queue)
            _, first_pos = queue[0]
            for i in range(level_length):
                node, pos = queue.popleft()
                if node.left:
                    queue.append((node.left, 2 * pos))
                if node.right:
                    queue.append((node.right, 2 * pos + 1))
            max_width = max(max_width, pos - first_pos + 1)
        
        return max_width

Input: left = 10, right = 15
Output: 5

def countPrimeSetBits(left, right):
    def countBits(x):
        return bin(x).count('1')
    
    def isPrime(x):
        if x < 2:
            return False
        for i in range(2, int(x ** 0.5) + 1):
            if x % i == 0:
                return False
        return True
    
    count = 0
    for num in range(left, right + 1):
        if isPrime(countBits(num)):
            count += 1

Input: n = 3, k = 1
Output: [1,2,3]
Explanation: The [1,2,3] has three different positive integers ranging from 1 to 3, and the [1,1] has exactly 1 distinct integer: 1

def constructArray(n, k):
    answer = []
    left, right = 1, n
    
    for i in range(k + 1):
        if i % 2 == 0:
            answer.append(left)
            left += 1
        else:
            answer.append(right)
            right -= 1
    
    if k % 2 == 0:
        answer.extend(range(left, right + 1))
    else:
        answer.extend(range(right, left - 1, -1))
    
    return answer

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height) == 0:
            return 0
        ans = 0
        size = len(height)
        left_max, right_max = [0] * size, [0] * size
        left_max[0] = height[0]
        for i in range(1, size):
            left_max[i] = max(height[i], left_max[i - 1])
        right_max[size - 1] = height[size - 1]
        for i in range(size - 2, -1, -1):
            right_max[i] = max(height[i], right_max[i + 1])
        for i in range(1, size - 1):
            ans += min(left_max[i], right_max[i]) - height[i]
        return ans

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

def totalFruit(fruits):
    from collections import defaultdict
    basket = defaultdict(int)
    left = 0
    max_fruits = 0

    for right in range(len(fruits)):
        basket[fruits[right]] += 1
        while len(basket) > 2:
            basket[fruits[left]] -= 1
            if basket[fruits[left]] == 0:
                del basket[fruits[left]]
            left += 1
        max_fruits = max(max_fruits, right - left + 1)

    return max_fruits

Input: n = 3, k = 2, row = 0, column = 0
Output: 0.06250
Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board.
From each of those positions, there are also two moves that will keep the knight on the board.
The total probability the knight stays on the board is 0.0625.

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        directions = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]
        dp = [[[0] * n for _ in range(n)] for _ in range(k + 1)]
        dp[0][row][column] = 1

        for moves in range(1, k + 1):
            for i in range(n):
                for j in range(n):
                    for direction in directions:
                        prevI, prevJ = i - direction[0], j - direction[1]
                        if 0 <= prevI < n and 0 <= prevJ < n:
                            dp[moves][i][j] += dp[moves - 1][prevI][prevJ] / 8

        return sum(map(sum, dp[k]))