Tries

#Topic: Trie Basics — Insertion, Search, Prefix Check
#Time: O(m) Insertion/Search — m = word length
#Space: O(alphabet_size × max_len × n) Worst Case

from __future__ import annotations


class TrieNode:
    """Trie Node."""

    def __init__(self) -> None:
        self.children: dict[str, TrieNode] = {}
        self.is_end: bool = False   #Whether a word ends at this node


class Trie:
    """Implementation of Prefix Tree."""

    def __init__(self) -> None:
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        """Insert word.

        Time:  O(m) — m = word length
        Space: O(m) — up to m new nodes created"""
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word: str) -> bool:
        """Check if a word exists exactly in the trie.

        Time:  O(m)
        Space: O(1)"""
        node = self._find_node(word)
        return node is not None and node.is_end

    def starts_with(self, prefix: str) -> bool:
        """Check if there is a word that starts with the given prefix.

        Time:  O(m) — m = prefix length
        Space: O(1)"""
        return self._find_node(prefix) is not None

    def _find_node(self, prefix: str) -> TrieNode | None:
        """Return the node at the end of the prefix path (None if it doesn't exist).

        Time:  O(m)
        Space: O(1)"""
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

    def delete(self, word: str) -> bool:
        """Delete word. Preserve nodes shared with other words.

        Time:  O(m)
        Space: O(m) — recursive stack"""
        def _delete(node: TrieNode, word: str, depth: int) -> bool:
            """True if the current node can be deleted."""
            if depth == len(word):
                if not node.is_end:
                    return False   #No word exists
                node.is_end = False
                return len(node.children) == 0   #Can be deleted if no children

            ch = word[depth]
            if ch not in node.children:
                return False

            should_delete = _delete(node.children[ch], word, depth + 1)
            if should_delete:
                del node.children[ch]
                return not node.is_end and len(node.children) == 0

            return False

        return _delete(self.root, word, 0)

    def count_words(self) -> int:
        """Number of stored words.

        Time:  O(n × m)
        Space: O(h) — DFS stack"""
        def dfs(node: TrieNode) -> int:
            total = 1 if node.is_end else 0
            for child in node.children.values():
                total += dfs(child)
            return total

        return dfs(self.root)


#── Example Execution ──────────────────────────────────────────────────────────────
if __name__ == "__main__":
    trie = Trie()
    words = ["apple", "app", "apt", "bat", "ball", "band"]

    print("=== Insertion ===")
    for w in words:
        trie.insert(w)
        print(f"  insert('{w}')")

    print("=== Word Search ===")
    test_words = ["app", "apple", "ap", "appl", "bat", "ba", "ban"]
    for w in test_words:
        found = trie.search(w)
        print(f"  search('{w}'): {found}")

    print("=== Prefix Check ===")
    prefixes = ["ap", "app", "b", "ba", "bal", "bx", ""]
    for p in prefixes:
        exists = trie.starts_with(p)
        print(f"  starts_with('{p}'): {exists}")

    print(f"Total stored words: {trie.count_words()}")

    print("=== Deletion ===")
    print(f"  delete('app'): {trie.delete('app')}")
    print(f"  search('app'): {trie.search('app')}")
    print(f"  search('apple'): {trie.search('apple')}")  #Must still exist
    print(f"Total words: {trie.count_words()}")

#Subject: Trie Autocomplete
#Time: O(m + number of results) Autocomplete — m = prefix length
#Space: O(n × m) Trie storage

from __future__ import annotations


class TrieNode:
    def __init__(self) -> None:
        self.children: dict[str, TrieNode] = {}
        self.is_end: bool = False
        self.word: str = ""   #Store the full word at the end node of a word


class AutocompleteTrie:
    """Trie with autocomplete feature."""

    def __init__(self) -> None:
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        """Insert a word.

        Time:  O(m)
        Space: O(m)"""
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True
        node.word = word

    def autocomplete(self, prefix: str, max_results: int = 10) -> list[str]:
        """Return all words starting with a prefix (in alphabetical order).

        Time:  O(m + T) — T = total number of nodes under the prefix
        Space: O(number of results + h)"""
        #Find the prefix node
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return []
            node = node.children[ch]

        #Collect all words using DFS
        results: list[str] = []
        self._collect_words(node, results, max_results)
        return sorted(results)

    def _collect_words(
        self,
        node: TrieNode,
        results: list[str],
        max_results: int,
    ) -> None:
        """Collect words using DFS."""
        if len(results) >= max_results:
            return
        if node.is_end:
            results.append(node.word)
        for ch in sorted(node.children.keys()):   #In alphabetical order
            self._collect_words(node.children[ch], results, max_results)

    def top_k_autocomplete(
        self,
        prefix: str,
        k: int = 5,
    ) -> list[str]:
        """Top k autocomplete (BFS — shorter words first).

        Time:  O(m + T)
        Space: O(T)"""
        from collections import deque

        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return []
            node = node.children[ch]

        results: list[str] = []
        queue: deque[TrieNode] = deque([node])

        while queue and len(results) < k:
            curr = queue.popleft()
            if curr.is_end:
                results.append(curr.word)
            for ch in sorted(curr.children.keys()):
                queue.append(curr.children[ch])

        return results


#── Example Execution ──────────────────────────────────────────────────────────────
if __name__ == "__main__":
    trie = AutocompleteTrie()

    #English word dictionary
    dictionary = [
        "apple", "application", "apply", "apt",
        "apartment", "append", "appear", "apple",
        "bat", "battle", "ball", "band", "bank",
        "can", "candy", "cancel", "cap",
        "do", "dog", "door", "double",
    ]

    for word in dictionary:
        trie.insert(word)

    print("=== Autocomplete ===")
    test_prefixes = ["app", "ap", "ba", "ca", "z"]
    for p in test_prefixes:
        suggestions = trie.autocomplete(p)
        print(f"  '{p}' → {suggestions}")

    print("\n=== Top 3 Autocomplete (shorter words first) ===")
    for p in ["app", "ba"]:
        top = trie.top_k_autocomplete(p, k=3)
        print(f"Top 3 for '{p}': {top}")

    print("\n=== Search Box Simulation ===")
    user_input = "appl"
    print(f"Input: '{user_input}'")
    suggestions = trie.autocomplete(user_input, max_results=5)
    print(f"Suggestions:")
    for i, s in enumerate(suggestions, 1):
        print(f"    {i}. {s}")

#Topic: Trie Count — Prefix Count, Word Frequency
#Time: O(m) Insertion/Prefix Count — m = word length
# Space: O(n × m)

from __future__ import annotations


class CountTrieNode:
    """Trie node with count functionality."""

    def __init__(self) -> None:
        self.children: dict[str, CountTrieNode] = {}
        self.is_end: bool = False
        self.prefix_count: int = 0   #Number of words passing through this node
        self.word_count: int = 0     #Number of words ending at this node (duplicates allowed)


class CountTrie:
    """Trie supporting prefix counts and word frequencies."""

    def __init__(self) -> None:
        self.root = CountTrieNode()

    def insert(self, word: str) -> None:
        """Insert a word (duplicates allowed — frequency count).

        Time:  O(m)
        Space: O(m)"""
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = CountTrieNode()
            node = node.children[ch]
            node.prefix_count += 1   #Increase pass count
        node.is_end = True
        node.word_count += 1

    def count_words_with_prefix(self, prefix: str) -> int:
        """Return the number of words starting with the given prefix.

        Time:  O(m)
        Space: O(1)"""
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return 0
            node = node.children[ch]
        return node.prefix_count

    def count_exact(self, word: str) -> int:
        """Return the exact insertion count of that word.

        Time:  O(m)
        Space: O(1)"""
        node = self.root
        for ch in word:
            if ch not in node.children:
                return 0
            node = node.children[ch]
        return node.word_count if node.is_end else 0

    def delete_one(self, word: str) -> bool:
        """Delete one word (decrease word_count by 1).

        Time:  O(m)
        Space: O(m) — recursive"""
        if self.count_exact(word) == 0:
            return False

        node = self.root
        for ch in word:
            node = node.children[ch]
            node.prefix_count -= 1
        node.word_count -= 1
        if node.word_count == 0:
            node.is_end = False
        return True

    def most_common_prefix(self) -> str:
        """The prefix shared by the most words (maximum prefix_count path).

        Time:  O(m_max)
        Space: O(1)"""
        node = self.root
        prefix = []
        while node.children:
            #Select the most shared child
            best_ch = max(
                node.children,
                key=lambda ch: node.children[ch].prefix_count,
            )
            best_node = node.children[best_ch]
            if best_node.prefix_count == node.prefix_count or node.is_end:
                break
            prefix.append(best_ch)
            node = best_node
        return "".join(prefix)


#── Example Execution ──────────────────────────────────────────────────────────────
if __name__ == "__main__":
    trie = CountTrie()

    #Insert word (including duplicates)
    words = [
        "apple", "apple", "apple",
        "application", "application",
        "apply",
        "apt", "apt",
        "banana", "band",
    ]

    for w in words:
        trie.insert(w)

    print("=== Prefix Count ===")
    prefixes = ["app", "ap", "appl", "apple", "b", "ba", "ban", "xyz"]
    for p in prefixes:
        cnt = trie.count_words_with_prefix(p)
        print(f"Number of words with prefix '{p}': {cnt}")

    print("=== Word Frequency ===")
    check_words = ["apple", "apply", "apt", "banana", "band", "app"]
    for w in check_words:
        cnt = trie.count_exact(w)
        print(f"Occurrences of '{w}': {cnt}")

    print("=== Count After Deletion ===")
    trie.delete_one("apple")
    print(f"After deleting 1 'apple': {trie.count_exact('apple')}")
    print(f"Number of words with prefix 'app': {trie.count_words_with_prefix('app')}")

    print(f"=== Most Common Prefix ===")
    print(f"  '{trie.most_common_prefix()}'")

#Topic: Trie Applications — Longest Common Prefix, XOR Trie (Maximum XOR Pair)
#Time: O(n×m) LCP, O(n×32) XOR Trie
#Space: O(n×m) or O(n×32)

from __future__ import annotations


#── 1. Longest Common Prefix (LCP) ──────────────────────────

class TrieNode:
    def __init__(self) -> None:
        self.children: dict[str, TrieNode] = {}
        self.is_end: bool = False
        self.pass_count: int = 0   #Number of words passing through this node


class LCPTrie:
    """Trie for calculating the longest common prefix."""

    def __init__(self) -> None:
        self.root = TrieNode()
        self.word_count = 0

    def insert(self, word: str) -> None:
        """Time: O(m)"""
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
            node.pass_count += 1
        node.is_end = True
        self.word_count += 1

    def longest_common_prefix(self) -> str:
        """The longest common prefix of all inserted words.

        Key point: Continue descending as long as there is only one child and all words pass through

        Time:  O(m_min) — length of the shortest word
        Space: O(1)"""
        node = self.root
        prefix = []

        while (
            len(node.children) == 1        #No branching
            and not node.is_end            #No word ends here
        ):
            ch = next(iter(node.children))
            next_node = node.children[ch]
            if next_node.pass_count < self.word_count:
                break
            prefix.append(ch)
            node = next_node

        return "".join(prefix)


def lcp_of_list(strs: list[str]) -> str:
    """Longest common prefix of a list of strings (without trie, O(n×m)).

    Time:  O(n × m_min)
    Space: O(1)"""
    if not strs:
        return ""

    trie = LCPTrie()
    for s in strs:
        trie.insert(s)
    return trie.longest_common_prefix()


#── 2. XOR Trie (Maximum XOR Pair) ─────────────────────────────────────────

class XORTrieNode:
    def __init__(self) -> None:
        self.children: dict[int, XORTrieNode] = {}   #0 or 1


class XORTrie:
    """Bit trie for finding the maximum XOR of integers.

    Store each integer as a 31-bit binary number (from MSB)."""

    BITS = 31

    def __init__(self) -> None:
        self.root = XORTrieNode()

    def insert(self, num: int) -> None:
        """Insert an integer into a bit trie.

        Time:  O(32)
        Space: O(32)"""
        node = self.root
        for i in range(self.BITS, -1, -1):
            bit = (num >> i) & 1
            if bit not in node.children:
                node.children[bit] = XORTrieNode()
            node = node.children[bit]

    def max_xor_with(self, num: int) -> int:
        """XOR value with the number in the trie that gives the maximum XOR with num.

        Move in the direction of the opposite bit at each bit to maximize XOR.

        Time:  O(32)
        Space: O(1)"""
        node = self.root
        xor_val = 0
        for i in range(self.BITS, -1, -1):
            bit = (num >> i) & 1
            opposite = 1 - bit
            if opposite in node.children:
                xor_val |= (1 << i)   #XOR = 1 at this bit
                node = node.children[opposite]
            elif bit in node.children:
                node = node.children[bit]
            else:
                break
        return xor_val


def max_xor_pair(nums: list[int]) -> tuple[int, int, int]:
    """Return the two numbers in an array with the maximum XOR and the XOR value.

    Time:  O(n × 32)
    Space: O(n × 32)"""
    if len(nums) < 2:
        return (0, 0, 0)

    trie = XORTrie()
    max_xor = 0
    best_pair = (nums[0], nums[1])

    trie.insert(nums[0])
    for i in range(1, len(nums)):
        xor_val = trie.max_xor_with(nums[i])
        if xor_val > max_xor:
            max_xor = xor_val
            best_pair = (nums[i], -1)   #Finding the exact pair requires additional work
        trie.insert(nums[i])

    return (best_pair[0], best_pair[1], max_xor)


#── Example Execution ──────────────────────────────────────────────────────────────
if __name__ == "__main__":
    print("=== Longest Common Prefix ===")
    test_cases = [
        ["flower", "flow", "flight"],
        ["dog", "racecar", "car"],
        ["interview", "interact", "interface", "internal"],
        ["a"],
        [],
    ]
    for words in test_cases:
        lcp = lcp_of_list(words)
        print(f"  {words} → '{lcp}'")

    print("=== XOR Trie ===")
    nums = [3, 10, 5, 25, 2, 8]
    trie = XORTrie()
    for n in nums:
        trie.insert(n)

    print("Array:", nums)
    print("Each number and maximum XOR value:")
    for n in nums:
        mx = trie.max_xor_with(n)
        print(f"{n:2d} ({bin(n):>10s}) → Maximum XOR = {mx:2d} ({bin(mx)})")

    print("Searching for maximum XOR pair:")
    _, _, best = max_xor_pair(nums)
    print(f"Maximum XOR value: {best}")

    #Brute-force check
    brute_max = 0
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            brute_max = max(brute_max, nums[i] ^ nums[j])
    print(f"Brute-force check result: {brute_max}")
    assert best == brute_max, "Result mismatch!"
    print("Result match ✓")