Blind 75 Strings, Backtracking, And Tries

Use two pointers. Invariant: all cleaned characters outside the active left/right range have already matched. Mistake to avoid: building complicated filtered state before asking whether extra memory is acceptable. Test empty after filtering, one character, mixed punctuation, mixed case, and a mismatch at the end.

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

Expand around each possible odd and even center. Invariant: after an expansion stops, the previous range was the longest palindrome for that center. Mistake to avoid: checking only odd centers, which misses strings like "bb". Test one character, all same characters, no palindrome longer than one, even length, and ties.

def longest_palindrome(s):
    best_left = best_right = 0

    def expand(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1

    for center in range(len(s)):
        for left, right in (expand(center, center), expand(center, center + 1)):
            if right - left > best_right - best_left:
                best_left, best_right = left, right
    return s[best_left:best_right + 1]

Maintain counts for the active window and shrink only while all required counts are satisfied. Invariant: when formed equals the number of required characters, the current window is valid and can be minimized from the left. Mistake to avoid: treating membership as a set and losing duplicate requirements like "AABC". Test impossible target, duplicate target characters, target longer than source, and the whole source as the only answer.

from collections import Counter, defaultdict

def min_window(s, t):
    need = Counter(t)
    have = defaultdict(int)
    required = len(need)
    formed = 0
    left = 0
    best = (float("inf"), 0, 0)

    for right, ch in enumerate(s):
        have[ch] += 1
        if ch in need and have[ch] == need[ch]:
            formed += 1

        while formed == required:
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right)
            drop = s[left]
            have[drop] -= 1
            if drop in need and have[drop] < need[drop]:
                formed -= 1
            left += 1

    if best[0] == float("inf"):
        return ""
    return s[best[1]:best[2] + 1]

Sort candidates, recurse with a start index, and keep the same start index when reusing a number. Invariant: each path is nondecreasing, so the same combination cannot appear in different orders. Mistake to avoid: recursing from index zero every time and producing permutations. Test target zero, no solution, exact one-candidate solution, and candidates larger than target.

def combination_sum(candidates, target):
    candidates.sort()
    out = []
    path = []

    def dfs(start, remaining):
        if remaining == 0:
            out.append(path.copy())
            return
        for i in range(start, len(candidates)):
            value = candidates[i]
            if value > remaining:
                break
            path.append(value)
            dfs(i, remaining - value)
            path.pop()

    dfs(0, target)
    return out

Backtrack from cells matching the first character. Invariant: the visited set or temporary board mark contains exactly the cells in the current prefix path. Mistake to avoid: forgetting to unmark a cell before returning, which corrupts sibling branches. Test repeated letters, word longer than cell count, diagonal-only matches, and a board where the first letter appears many times.

def exist(board, word):
    rows, cols = len(board), len(board[0])

    def dfs(r, c, i):
        if i == len(word):
            return True
        if r < 0 or r == rows or c < 0 or c == cols:
            return False
        if board[r][c] != word[i]:
            return False

        saved = board[r][c]
        board[r][c] = "#"
        found = (
            dfs(r + 1, c, i + 1)
            or dfs(r - 1, c, i + 1)
            or dfs(r, c + 1, i + 1)
            or dfs(r, c - 1, i + 1)
        )
        board[r][c] = saved
        return found

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

Each node maps characters to child nodes and has an end marker. Invariant: after inserting a word, every prefix path exists and only the full word's final node is terminal. Mistake to avoid: returning true for exact search when only a prefix exists. Test empty prefix, duplicate insert, prefix without full word, and overlapping words.

class Trie:
    def __init__(self):
        self.root = {}
        self.end = "*"

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node[self.end] = True

    def _walk(self, text):
        node = self.root
        for ch in text:
            if ch not in node:
                return None
            node = node[ch]
        return node

    def search(self, word):
        node = self._walk(word)
        return node is not None and self.end in node

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

Use DP over string positions or memoized DFS. Invariant: dp[i] means the prefix ending before index i can be segmented. Mistake to avoid: greedy longest prefix matching, which fails when an early shorter word enables the rest. Test repeated words, no solution with tempting prefixes, empty string if allowed, and full-string dictionary match.

def word_break(s, word_dict):
    words = set(word_dict)
    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 words:
                dp[i] = True
                break
    return dp[-1]

This maps to sliding window over tokens, not characters. State the invariant as: the active suffix contains no duplicate committed token IDs, and left never moves backward. Mention that real systems need stable token IDs, timestamps, and a policy for revised partials before the coding logic is meaningful.

Use a trie keyed by normalized command tokens or characters. Exact commands end at terminal nodes; partial hypotheses stay valid while their prefix path exists. In production, include normalization, locale, synonyms, command versioning, fallback behavior, and metrics for false rejects.

Backtracking explores a branching tree. The worst case can remain exponential even with clean code. A strong answer explains the branching factor, depth, duplicate-skipping rule, pruning condition, and input constraints. Then it names when memoization or DP changes the state graph from repeated search into cached subproblems.