Skip to content

Graphs -> De Bruijn Sequence

Overlap-state modeling where length-n windows become directed edges, and one Eulerian cycle linearizes into a universal sequence.

  • Topic slug: graphs/de-bruijn-sequence
  • Tutorial page: Open tutorial
  • Ladder page: Open ladder
  • Repo problems currently tagged here: 1
  • Repo companion pages: 5
  • Curated external problems: 1

Microtopics

  • de-bruijn-graph
  • overlap-states
  • binary-order-n
  • eulerian-construction
  • implicit-state-graph
  • window-cover-construction

Learning Sources

Source Type
Competitive Programmer's Handbook PDF Reference
CSES De Bruijn Sequence Practice
CP-Algorithms Eulerian Path Reference

Repo Companion Material

Material Type
De Bruijn Sequence hot sheet quick reference
De Bruijn Sequence note flagship note
Eulerian Path / Cycle tutorial compare point
Graph Modeling tutorial compare point
Template Library exact starter route starter route

Curated External Problems

Core

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
De Bruijn Sequence CSES Hard Graph Modeling, Construction State Graph Modeling; Eulerian Construction; String Reconstruction Eulerian Cycle; Bitmask States De Bruijn Graph; Eulerian Cycle; Bitmask States The clean binary flagship where overlap-state modeling is the whole trick, and an Eulerian cycle is only the execution engine after the graph is revealed.

Repo Problems

Code Title Fit Difficulty Pattern Note Solution
DEBRUIJNSEQUENCE De Bruijn Sequence primary hard - Note Code

Regeneration

python3 scripts/generate_problem_catalog.py