Nim

Part 3 is a recursive solution with caching (memoization).

proc isValid(name: string, rules: Table[char, set[char]]): bool =
  for i in 0 ..< name.high:
    if name[i+1] notin rules[name[i]]: return false
  true

proc allNames(prefix: string, rules: Table[char, set[char]], range: Slice[int]): int =
  var memo {.global.}: Table[(int, char), int]
  if prefix.len >= range.b: return
  if (prefix.len, prefix[^1]) in memo: return memo[(prefix.len, prefix[^1])]

  for ch in rules.getOrDefault(prefix[^1]):
    if prefix.len + 1 >= range.a:
      inc result
    result += allNames(prefix & ch, rules, range)

  memo[(prefix.len, prefix[^1])] = result

proc solve_part1*(input: string): Solution =
  let (names, rules) = parseInput(input)
  for name in names:
    if name.isValid(rules):
      return Solution(kind: skString, strVal: name)

proc solve_part2*(input: string): Solution =
  let (names, rules) = parseInput(input)
  for ni, name in names:
    if name.isValid(rules):
      result.intVal += ni + 1

proc solve_part3*(input: string): Solution =
  let (names, rules) = parseInput(input)
  var seen: seq[string]
  for name in names:
    if not name.isValid(rules): continue
    if seen.anyIt(name.startsWith it): continue
    result.intVal += allNames(name, rules, 7..11)
    seen.add name

Full solution at Codeberg: solution.nim