Apple Leetcode Study Guide

def length_of_longest_substring(s: str) -> int:
    """
    Returns the length of the longest substring without repeating characters.

    Args:
    s (str): The input string.

    Returns:
    int: The length of the longest substring without repeating characters.
    """
    char_set = set()
    left = 0
    result = 0

    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        result = max(result, right - left + 1)

    return result

def longest_common_prefix(strs: list[str]) -> str:
    """
    Returns the longest common prefix among an array of strings.

    Args:
    strs (list[str]): The list of strings.

    Returns:
    str: The longest common prefix.
    """
    if not strs:
        return ""

    shortest_str = min(strs, key=len)

    for i, char in enumerate(shortest_str):
        for other in strs:
            if other[i] != char:
                return shortest_str[:i]

    return shortest_str

def is_valid(s: str) -> bool:
    """
    Returns True if the input string is valid, False otherwise.

    Args:
    s (str): The input string.

    Returns:
    bool: True if the input string is valid, False otherwise.
    """
    stack = []
    mapping = {")": "(", "}": "{", "]": "["}

    for char in s:
        if char in mapping.values():
            stack.append(char)
        elif char in mapping:
            if not stack or mapping[char] != stack.pop():
                return False

    return not stack

def trap(height: list[int]) -> int:
    """
    Returns the amount of water that can be trapped.

    Args:
    height (list[int]): The list of heights.

    Returns:
    int: The amount of water that can be trapped.
    """
    if not height:
        return 0

    left, right = 0, len(height) - 1
    max_left, max_right = height[left], height[right]
    result = 0

    while left <= right:
        max_left = max(max_left, height[left])
        max_right = max(max_right, height[right])

        if max_left < max_right:
            result += max_left - height[left]
            left += 1
        else:
            result += max_right - height[right]
            right -= 1

    return result

def group_anagrams(strs: list[str]) -> list[list[str]]:
    """
    Returns the grouped anagrams.

    Args:
    strs (list[str]): The list of strings.

    Returns:
    list[list[str]]: The grouped anagrams.
    """
    anagrams = {}

    for s in strs:
        sorted_s = "".join(sorted(s))
        if sorted_s in anagrams:
            anagrams[sorted_s].append(s)
        else:
            anagrams[sorted_s] = [s]

    return list(anagrams.values())

def merge(intervals: list[list[int]]) -> list[list[int]]:
    """
    Returns the merged intervals.

    Args:
    intervals (list[list[int]]): The list of intervals.

    Returns:
    list[list[int]]: The merged intervals.
    """
    if not intervals:
        return []

    intervals.sort(key=lambda x: x[0])

    merged = [intervals[0]]

    for current in intervals[1:]:
        if merged[-1][1] >= current[0]:
            merged[-1][1] = max(merged[-1][1], current[1])
        else:
            merged.append(current)

    return merged

def max_profit(prices: list[int]) -> int:
    """
    Returns the maximum profit.

    Args:
    prices (list[int]): The list of prices.

    Returns:
    int: The maximum profit.
    """
    if not prices:
        return 0

    min_price = prices[0]
    max_profit = 0

    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)

    return max_profit

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        """
        Initializes the LRU cache.

        Args:
        capacity (int): The capacity of the cache.
        """
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key: int) -> int:
        """
        Returns the value of the key if it exists in the cache.

        Args:
        key (int): The key.

        Returns:
        int: The value of the key if it exists, -1 otherwise.
        """
        if key in self.cache:
            value = self.cache.pop(key)
            self.cache[key] = value
            return value
        return -1

    def put(self, key: int, value: int) -> None:
        """
        Sets the value of the key.

        Args:
        key (int): The key.
        value (int): The value.
        """
        if key in self.cache:
            self.cache.pop(key)
        elif len(self.cache) >= self.capacity:
            self.cache.popitem(last=False)
        self.cache[key] = value

def reverse_words(s: str) -> str:
    """
    Returns the string with the words reversed.

    Args:
    s (str): The input string.

    Returns:
    str: The string with the words reversed.
    """
    words = s.split()
    return " ".join(reversed(words))

def num_islands(grid: list[list[str]]) -> int:
    """
    Returns the number of islands.

    Args:
    grid (list[list[str]]): The 2D grid.

    Returns:
    int: The number of islands.
    """
    if not grid:
        return 0

    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                dfs(grid, i, j)
                count += 1

    return count

def dfs(grid: list[list[str]], i: int, j: int) -> None:
    """
    Performs a depth-first search on the grid.

    Args:
    grid (list[list[str]]): The 2D grid.
    i (int): The current row.
    j (int): The current column.
    """
    if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] != '1':
        return
    grid[i][j] = '#'
    dfs(grid, i+1, j)
    dfs(grid, i-1, j)
    dfs(grid, i, j+1)
    dfs(grid, i, j-1)

from collections import defaultdict

def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
    """
    Returns True if it's possible to finish all courses, False otherwise.

    Args:
    num_courses (int): The number of courses.
    prerequisites (list[list[int]]): The list of prerequisites.

    Returns:
    bool: True if it's possible to finish all courses, False otherwise.
    """
    graph = defaultdict(list)
    visited = [0] * num_courses

    for x, y in prerequisites:
        graph[x].append(y)

    def dfs(node: int) -> bool:
        if visited[node] == -1:
            return False
        if visited[node] == 1:
            return True

        visited[node] = -1
        for neighbor in graph[node]:
            if not dfs(neighbor):
                return False
        visited[node] = 1
        return True

    for i in range(num_courses):
        if not dfs(i):
            return False

    return True

def product_except_self(nums: list[int]) -> list[int]:
    """
    Returns the product of all numbers except self.

    Args:
    nums (list[int]): The list of numbers.

    Returns:
    list[int]: The product of all numbers except self.
    """
    n = len(nums)
    answer = [1] * n

    prefix_product = 1
    for i in range(n):
        answer[i] *= prefix_product
        prefix_product *= nums[i]

    suffix_product = 1
    for i in range(n-1, -1, -1):
        answer[i] *= suffix_product
        suffix_product *= nums[i]

    return answer

from collections import defaultdict

def subarray_sum(nums: list[int], k: int) -> int:
    """
    Returns the total number of continuous subarrays whose sum equals to k.

    Args:
    nums (list[int]): The list of numbers.
    k (int): The target sum.

    Returns:
    int: The total number of continuous subarrays whose sum equals to k.
    """
    count = 0
    prefix_sum_count = defaultdict(int)
    prefix_sum = 0

    for num in nums:
        prefix_sum += num
        if prefix_sum - k in prefix_sum_count:
            count += prefix_sum_count[prefix_sum - k]
        prefix_sum_count[prefix_sum] += 1

    return count

class MyHashMap:
    def __init__(self):
        """
        Initializes the HashMap.
        """
        self.size = 1000
        self.buckets = [[] for _ in range(self.size)]

    def put(self, key: int, value: int) -> None:
        """
        Sets the value of the key.

        Args:
        key (int): The key.
        value (int): The value.
        """
        index = key % self.size
        bucket = self.buckets[index]

        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return

        bucket.append((key, value))

    def get(self, key: int) -> int:
        """
        Returns the value of the key.

        Args:
        key (int): The key.

        Returns:
        int: The value of the key if it exists, -1 otherwise.
        """
        index = key % self.size
        bucket = self.buckets[index]

        for k, v in bucket:
            if k == key:
                return v

        return -1

    def remove(self, key: int) -> None:
        """
        Removes the key.

        Args:
        key (int): The key.
        """
        index = key % self.size
        bucket = self.buckets[index]

        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                return

import heapq

def min_meeting_rooms(intervals: list[list[int]]) -> int:
    """
    Returns the minimum number of rooms required.

    Args:
    intervals (list[list[int]]): The list of intervals.

    Returns:
    int: The minimum number of rooms required.
    """
    if not intervals:
        return 0

    intervals.sort(key=lambda x: x[0])

    end_times = [intervals[0][1]]
    heapq.heapify(end_times)

    for interval in intervals[1:]:
        if interval[0] >= end_times[0]:
            heapq.heappop(end_times)
        heapq.heappush(end_times, interval[1])

    return len(end_times)

def move_zeroes(nums: list[int]) -> None:
    """
    Moves all 0's to the end of the array.

    Args:
    nums (list[int]): The list of numbers.
    """
    left = 0
    for right in range(len(nums)):
        if nums[right] != 0:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1

def two_sum(numbers: list[int], target: int) -> list[int]:
    """
    Returns the 2-sum indices.

    Args:
    numbers (list[int]): The list of numbers.
    target (int): The target sum.

    Returns:
    list[int]: The 2-sum indices.
    """
    left, right = 0, len(numbers) - 1

    while left < right:
        current_sum = numbers[left] + numbers[right]
        if current_sum == target:
            return [left + 1, right + 1]
        elif current_sum < target:
            left += 1
        else:
            right -= 1

def full_justify(words: list[str], max_width: int) -> list[str]:
    """
    Returns the justified text.

    Args:
    words (list[str]): The list of words.
    max_width (int): The maximum width.

    Returns:
    list[str]: The justified text.
    """
    result = []
    current_line = []
    current_width = 0

    for word in words:
        if current_width + len(current_line) + len(word) > max_width:
            result.append(justify_line(current_line, max_width))
            current_line = []
            current_width = 0
        current_line.append(word)
        current_width += len(word)

    result.append(justify_last_line(current_line, max_width))
    return result

def justify_line(line: list[str], max_width: int) -> str:
    """
    Justifies a line of text.

    Args:
    line (list[str]): The line of text.
    max_width (int): The maximum width.

    Returns:
    str: The justified line.
    """
    total_chars = sum(len(word) for word in line)
    num_gaps = max_width - total_chars
    num_words = len(line)

    if num_words == 1:
        return line[0] + " " * num_gaps

    gap_size = num_gaps // (num_words - 1)
    extra_gaps = num_gaps % (num_words - 1)

    justified_line = ""
    for i, word in enumerate(line):
        justified_line += word
        if i < num_words - 1:
            justified_line += " " * (gap_size + (1 if i < extra_gaps else 0))

    return justified_line

def justify_last_line(line: list[str], max_width: int) -> str:
    """
    Justifies the last line of text.

    Args:
    line (list[str]): The line of text.
    max_width (int): The maximum width.

    Returns:
    str: The justified last line.
    """
    last_line = " ".join(line)
    return last_line + " " * (max_width - len(last_line))

def is_match(s: str, p: str) -> bool:
    """
    Returns True if the string matches the pattern, False otherwise.

    Args:
    s (str): The input string.
    p (str): The pattern.

    Returns:
    bool: True if the string matches the pattern, False otherwise.
    """
    dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
    dp[-1][-1] = True

    for i in range(len(s), -1, -1):
        for j in range(len(p) - 1, -1, -1):
            match = i < len(s) and (p[j] == s[i] or p[j] == '.')
            if j + 1 < len(p) and p[j + 1] == '*':
                dp[i][j] = dp[i][j + 2] or match and dp[i + 1][j]
            else:
                dp[i][j] = match and dp[i + 1][j + 1]

    return dp[0][0]

class TicTacToe:
    def __init__(self, n: int):
        """
        Initializes the Tic-Tac-Toe.

        Args:
        n (int): The size of the board.
        """
        self.n = n
        self.rows = [0] * n
        self.cols = [0] * n
        self.diag = 0
        self.anti_diag = 0

    def move(self, row: int, col: int, player: int) -> None:
        """
        Makes a move.

        Args:
        row (int): The row.
        col (int): The column.
        player (int): The player.
        """
        value = 1 if player == 1 else -1

        self.rows[row] += value
        self.cols[col] += value

        if row == col:
            self.diag += value
        if row + col == self.n - 1:
            self.anti_diag += value

        if (self.rows[row] == self.n * value or
            self.cols[col] == self.n * value or
            self.diag == self.n * value or
            self.anti_diag == self.n * value):
            return True

        return False

def is_palindrome(s: str) -> bool:
    """
    Returns True if the string is a palindrome, False otherwise.

    Args:
    s (str): The string.

    Returns:
    bool: True if the string is a palindrome, False otherwise.
    """
    left, right = 0, len(s) - 1

    while left < right:
        if not s[left].isalnum():
            left += 1
        elif not s[right].isalnum():
            right -= 1
        elif s[left].lower() != s[right].lower():
            return False
        else:
            left += 1
            right -= 1

    return True

class MyCircularQueue:
    def __init__(self, k: int):
        """
        Initializes the Circular Queue.

        Args:
        k (int): The capacity.
        """
        self.k = k
        self.queue = [0] * k
        self.head = 0
        self.tail = 0
        self.size = 0

    def en_queue(self, value: int) -> bool:
        """
        Enqueues a value.

        Args:
        value (int): The value.

        Returns:
        bool: True if the operation is successful, False otherwise.
        """
        if self.size == self.k:
            return False
        self.queue[self.tail] = value
        self.tail = (self.tail + 1) % self.k
        self.size += 1
        return True

    def de_queue(self) -> bool:
        """
        Dequeues a value.

        Returns:
        bool: True if the operation is successful, False otherwise.
        """
        if self.size == 0:
            return False
        self.head = (self.head + 1) % self.k
        self.size -= 1
        return True

    def Front(self) -> int:
        """
        Returns the front of the queue.

        Returns:
        int: The front of the queue if it is not empty, -1 otherwise.
        """
        if self.size == 0:
            return -1
        return self.queue[self.head]

    def Rear(self) -> int:
        """
        Returns the rear of the queue.

        Returns:
        int: The rear of the queue if it is not empty, -1 otherwise.
        """
        if self.size == 0:
            return -1
        return self.queue[(self.tail - 1) % self.k]

    def is_empty(self) -> bool:
        """
        Returns True if the queue is empty, False otherwise.

        Returns:
        bool: True if the queue is empty, False otherwise.
        """
        return self.size == 0

    def is_full(self) -> bool:
        """
        Returns True if the queue is full, False otherwise.

        Returns:
        bool: True if the queue is full, False otherwise.
        """
        return self.size == self.k

import heapq
from collections import Counter

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    """
    Returns the k most frequent elements.

    Args:
    nums (list[int]): The list of numbers.
    k (int): The number of elements.

    Returns:
    list[int]: The k most frequent elements.
    """
    count = Counter(nums)
    return heapq.nlargest(k, count.keys(), key=count.get)

def fib(n: int) -> int:
    """
    Returns the nth Fibonacci number.

    Args:
    n (int): The index.

    Returns:
    int: The nth Fibonacci number.
    """
    if n <= 1:
        return n

    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b

    return b

from collections import deque

def ladder_length(begin_word: str, end_word: str, word_list: list[str]) -> int:
    """
    Returns the length of the shortest transformation sequence.

    Args:
    begin_word (str): The beginning word.
    end_word (str): The end word.
    word_list (list[str]): The list of words.

    Returns:
    int: The length of the shortest transformation sequence.
    """
    word_set = set(word_list)
    queue = deque([(begin_word, 1)])

    while queue:
        word, length = queue.popleft()

        if word == end_word:
            return length

        for i in range(len(word)):
            for char in 'abcdefghijklmnopqrstuvwxyz':
                next_word = word[:i] + char + word[i+1:]
                if next_word in word_set:
                    word_set.remove(next_word)
                    queue.append((next_word, length + 1))

    return 0

def three_sum(nums: list[int]) -> list[list[int]]:
    """
    Returns all the triplets.

    Args:
    nums (list[int]): The list of numbers.

    Returns:
    list[list[int]]: All the triplets.
    """
    nums.sort()
    result = []

    for i in range(len(nums)):
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left, right = i + 1, len(nums) - 1

        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1

    return result

from collections import defaultdict, deque

def find_order(numCourses, prerequisites):
    """
    Returns the ordering of courses to finish all courses.

    Args:
    numCourses (int): The number of courses.
    prerequisites (list): A list of pairs, where each pair [a, b] means course a requires course b.

    Returns:
    list: A list of course IDs in the order to finish all courses. If it's impossible, return an empty list.
    """
    graph = defaultdict(list)
    indegree = [0] * numCourses
    for x, y in prerequisites:
        graph[y].append(x)
        indegree[x] += 1

    queue = deque([i for i in range(numCourses) if indegree[i] == 0])
    result = []
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    return result if len(result) == numCourses else []

import heapq

def findKthLargest(nums, k):
    """
    Returns the kth largest element in the given array.

    Args:
    nums (list): The input list of integers.
    k (int): The index of the largest element to find (1-indexed).

    Returns:
    int: The kth largest element in the array.
    """
    return heapq.nlargest(k, nums)[-1]

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class Trie:
    def __init__(self):
        """
        Initializes the trie data structure.
        """
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_word = True

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_word

    def starts_with(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

import heapq

def findCheapestPrice(n, flights, src, dst, k):
    """
    Returns the cheapest price to fly from src to dst with at most k stops.

    Args:
    n (int): The number of cities.
    flights (list): A list of flights, where each flight is a list [city1, city2, price].
    src (int): The source city.
    dst (int): The destination city.
    k (int): The maximum number of stops.

    Returns:
    int: The cheapest price to fly from src to dst with at most k stops. If there is no such route, return -1.
    """
    prices = [float('inf')] * n
    prices[src] = 0
    for _ in range(k + 1):
        temp = prices[:]
        for u, v, w in flights:
            temp[v] = min(temp[v], prices[u] + w)
        prices = temp

    return prices[dst] if prices[dst] != float('inf') else -1

def wordBreak(s, word_dict):
    """
    Returns True if the given string can be segmented into a space-separated sequence of dictionary words.

    Args:
    s (str): The input string.
    word_dict (list): A list of dictionary words.

    Returns:
    bool: True if the string can be segmented, False otherwise.
    """
    dp = [False] * (len(s) + 1)
    dp[0] = True
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_dict:
                dp[i] = True
                break
    return dp[-1]

import heapq

class MedianFinder:
    def __init__(self):
        """
        Initializes the MedianFinder data structure.
        """
        self.max_heap = []
        self.min_heap = []

    def add_num(self, num: int) -> None:
        if not self.max_heap or num <= -self.max_heap[0]:
            heapq.heappush(self.max_heap, -num)
        else:
            heapq.heappush(self.min_heap, num)
        if len(self.max_heap) > len(self.min_heap) + 1:
            heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
        elif len(self.min_heap) > len(self.max_heap):
            heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))

    def find_median(self) -> float:
        if len(self.max_heap) == len(self.min_heap):
            return (-self.max_heap[0] + self.min_heap[0]) / 2.0
        return -self.max_heap[0]

def roman_to_int(s: str) -> int:
    """
    Converts a Roman numeral string to an integer.

    Args:
    s (str): The input Roman numeral string.

    Returns:
    int: The integer value of the Roman numeral string.
    """
    roman_dict = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    result = 0
    for i in range(len(s)):
        if i > 0 and roman_dict[s[i]] > roman_dict[s[i - 1]]:
            result += roman_dict[s[i]] - 2 * roman_dict[s[i - 1]]
        else:
            result += roman_dict[s[i]]
    return result

def spiral_order(matrix):
    """
    Returns a list of integers representing the spiral order traversal of the given matrix.

    Args:
    matrix (list): A 2D list of integers.

    Returns:
    list: A list of integers representing the spiral order traversal.
    """
    result = []
    if not matrix:
        return result

    top, bottom, left, right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1
    while top <= bottom and left <= right:
        for i in range(left, right + 1):
            result.append(matrix[top][i])
        top += 1
        for i in range(top, bottom + 1):
            result.append(matrix[i][right])
        right -= 1
        if top <= bottom:
            for i in range(right, left - 1, -1):
                result.append(matrix[bottom][i])
            bottom -= 1
        if left <= right:
            for i in range(bottom, top - 1, -1):
                result.append(matrix[i][left])
            left += 1
    return result

class MinStack:
    def __init__(self):
        """
        Initializes the MinStack data structure.
        """
        self.stack = []
        self.min_stack = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)

    def pop(self) -> None:
        if self.stack:
            if self.stack[-1] == self.min_stack[-1]:
                self.min_stack.pop()
            self.stack.pop()

    def top(self) -> int:
        return self.stack[-1] if self.stack else None

    def get_min(self) -> int:
        return self.min_stack[-1] if self.min_stack else None

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

class Solution:
    def diameter_of_binary_tree(self, root):
        """
        Returns the diameter of the given binary tree.

        Args:
        root (TreeNode): The root of the binary tree.

        Returns:
        int: The diameter of the binary tree.
        """
        self.diameter = 0

        def depth(node):
            if not node:
                return 0
            left_depth = depth(node.left)
            right_depth = depth(node.right)
            self.diameter = max(self.diameter, left_depth + right_depth)
            return 1 + max(left_depth, right_depth)

        depth(root)
        return self.diameter

def search_range(nums, target):
    """
    Returns the first and last position of the target value in the given sorted array.

    Args:
    nums (list): A sorted list of integers.
    target (int): The target value.

    Returns:
    list: A list containing the first and last position of the target value. If the target is not found, return [-1, -1].
    """
    def binary_search(nums, target, find_first):
        left, right = 0, len(nums) - 1
        result = -1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                result = mid
                if find_first:
                    right = mid - 1
                else:
                    left = mid + 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return result

    return [binary_search(nums, target, True), binary_search(nums, target, False)]

# The guess API is already defined for you.
# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
# def guess(word: ''):
from collections import Counter

class Solution:
    def findSecretWord(self, words, master):
        """
        :type words: List[str]
        :type master: Master
        :rtype: None
        """
        
        def match_count(word1, word2):
            # Returns how many positions match between two words
            return sum(c1 == c2 for c1, c2 in zip(word1, word2))
        
        # As the problem ensures that a solution is always possible
        for _ in range(10):  # At most 10 guesses (allowedGuesses limit)
            # Use a frequency count of all characters for more informed guesses
            # (can improve performance intuitively, but not required)
            count = [0] * len(words[0])  # Keep track of character distributions in words
            for word in words:
                for i, c in enumerate(word):
                    count[i] += 1
            
            # Choose a word to guess by minimizing potential elimination (heuristics-based)
            # Use the word with the highest "score" based on character frequencies
            best_word = max(words, key=lambda word: sum(count[i] for i, c in enumerate(word)))
            
            # Make a guess
            matches = master.guess(best_word)
            if matches == len(best_word):  # Success case
                return
            
            # Filter remaining possibilities based on the match count
            words = [word for word in words if match_count(best_word, word) == matches]

def coinChange(coins, amount):
    """
    Returns the fewest number of coins that sum up to the given amount.

    Args:
    coins (list): A list of coin denominations.
    amount (int): The target amount.

    Returns:
    int: The fewest number of coins. If it's impossible, return -1.
    """
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)

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

from collections import Counter

def leastInterval(tasks, n):
    """
    Returns the minimum time to schedule the given tasks.

    Args:
    tasks (list): A list of tasks.
    n (int): The cooldown period.

    Returns:
    int: The minimum time to schedule the tasks.
    """
    count = Counter(tasks)
    max_freq = max(count.values())
    max_freq_tasks = sum(value == max_freq for value in count.values())

    return max(len(tasks), (max_freq - 1) * (n + 1) + max_freq_tasks)

def insert(intervals, new_interval):
    """
    Inserts a new interval into the given list of intervals and merges the overlapping intervals.

    Args:
    intervals (list): A list of intervals.
    new_interval (list): The new interval to insert.

    Returns:
    list: The updated list of merged intervals.
    """
    result = []
    i = 0
    while i < len(intervals) and intervals[i][1] < new_interval[0]:
        result.append(intervals[i])
        i += 1

    while i < len(intervals) and intervals[i][0] <= new_interval[1]:
        new_interval[0] = min(new_interval[0], intervals[i][0])
        new_interval[1] = max(new_interval[1], intervals[i][1])
        i += 1

    result.append(new_interval)
    result.extend(intervals[i:])

    return result

def maxProfit(prices):
    """
    Returns the maximum profit from buying and selling stocks.

    Args:
    prices (list): A list of stock prices.

    Returns:
    int: The maximum profit.
    """
    result = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            result += prices[i] - prices[i - 1]

    return result

def search(nums, target):
    """
    Returns the index of the target value in the given rotated sorted array.

    Args:
    nums (list): A rotated sorted list of integers.
    target (int): The target value.

    Returns:
    int: The index of the target value. If not found, return -1.
    """
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

from collections import defaultdict, deque

def find_ladders(begin_word, end_word, word_list):
    """
    Returns all possible shortest transformation sequences from the begin_word to the end_word.

    Args:
    begin_word (str): The starting word.
    end_word (str): The target word.
    word_list (list): A list of words.

    Returns:
    list: A list of lists, where each sublist is a transformation sequence.
    """
    word_set = set(word_list)
    queue = deque([(begin_word, [begin_word])])
    result = []
    found = False

    while queue:
        level_size = len(queue)
        level_words = set()
        for _ in range(level_size):
            word, path = queue.popleft()
            for i in range(len(word)):
                for char in 'abcdefghijklmnopqrstuvwxyz':
                    next_word = word[:i] + char + word[i + 1:]
                    if next_word == end_word:
                        result.append(path + [next_word])
                        found = True
                    if next_word in word_set and next_word not in level_words:
                        queue.append((next_word, path + [next_word]))
                        level_words.add(next_word)
        if found:
            break
        word_set -= level_words

    return result

def exist(board, word):
    """
    Returns True if the given word exists in the grid.

    Args:
    board (list): A 2D list of characters.
    word (str): The target word.

    Returns:
    bool: True if the word exists, False otherwise.
    """
    def dfs(i, j, k):
        if k == len(word):
            return True
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or word[k] != board[i][j]:
            return False
        temp = board[i][j]
        board[i][j] = '#'
        found = dfs(i - 1, j, k + 1) or dfs(i + 1, j, k + 1) or dfs(i, j - 1, k + 1) or dfs(i, j + 1, k + 1)
        board[i][j] = temp
        return found

    for i in range(len(board)):
        for j in range(len(board[0])):
            if dfs(i, j, 0):
                return True

    return False