"""Prefix trie with insert/search/startsWith/delete and prefix enumeration.

Correctness notes:
- delete only removes nodes that are not shared by other words; marks end-of-word
  flags rather than blindly removing.
- search is exact word match; starts_with is prefix match.
- words_with_prefix returns sorted list (deterministic).
- Empty string is a valid word if inserted.
- count_prefix counts DISTINCT words, so for every prefix p it equals
  len(words_with_prefix(p)); a duplicate insert adds no word and a delete
  removes one. It is maintained incrementally along the path, not recomputed.
"""
from __future__ import annotations


class _Node:
    __slots__ = ("children", "is_end", "count")

    def __init__(self):
        self.children: dict[str, "_Node"] = {}
        self.is_end: bool = False
        self.count: int = 0  # number of distinct words passing through this node


class Trie:
    def __init__(self):
        self.root = _Node()

    def _path(self, word: str) -> list["_Node"]:
        """Nodes along `word`, root included; missing nodes are created."""
        node = self.root
        path = [node]
        for ch in word:
            node = node.children.setdefault(ch, _Node())
            path.append(node)
        return path

    def _path_existing(self, word: str) -> list["_Node"]:
        """Nodes along an existing `word`, root included. Creates nothing."""
        node = self.root
        path = [node]
        for ch in word:
            node = node.children[ch]
            path.append(node)
        return path

    def insert(self, word: str) -> None:
        path = self._path(word)
        last = path[-1]
        if last.is_end:
            return  # already a distinct word: the count must not move
        last.is_end = True
        for node in path:
            node.count += 1

    def search(self, word: str) -> bool:
        node = self._walk(word)
        return node is not None and node.is_end

    def starts_with(self, prefix: str) -> bool:
        return self._walk(prefix) is not None

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

    def delete(self, word: str) -> bool:
        # returns True if word was present and removed
        node = self._walk(word)
        if node is None or not node.is_end:
            return False
        node.is_end = False
        for n in self._path_existing(word):
            n.count -= 1
        self._prune(self.root, word, 0)  # drop branches that carry no word
        return True

    def _prune(self, node: _Node, word: str, depth: int) -> bool:
        """Return True when `node` itself may be removed from its parent."""
        if depth == len(word):
            return (not node.is_end) and len(node.children) == 0
        ch = word[depth]
        child = node.children.get(ch)
        if child is None:
            return False
        if self._prune(child, word, depth + 1):
            del node.children[ch]
            return (not node.is_end) and len(node.children) == 0
        return False

    def words_with_prefix(self, prefix: str) -> list[str]:
        node = self._walk(prefix)
        if node is None:
            return []
        out: list[str] = []
        self._collect(node, prefix, out)
        return sorted(out)

    def _collect(self, node: _Node, prefix: str, out: list[str]) -> None:
        if node.is_end:
            out.append(prefix)
        for ch in sorted(node.children):
            self._collect(node.children[ch], prefix + ch, out)

    def count_prefix(self, prefix: str) -> int:
        """Distinct words having `prefix`; count_prefix("") == len(self)."""
        node = self._walk(prefix)
        return node.count if node is not None else 0

    def __len__(self) -> int:
        # number of distinct words
        out = [0]

        def dfs(n):
            if n.is_end:
                out[0] += 1
            for c in n.children.values():
                dfs(c)

        dfs(self.root)
        return out[0]


if __name__ == "__main__":
    t = Trie()
    for w in ["cat", "car", "card", "dog"]:
        t.insert(w)
    print(t.search("car"), t.starts_with("ca"), t.words_with_prefix("ca"))
    t.delete("car")
    print(t.search("car"), t.search("card"))