A fundamental operation in computational genomics is to reduce the input sequences to their constituentk-mers. For maximum performance of downstream applications it is important to store thek-mers in small space, while keeping the representation easy and efficient to use (i.e. withoutk-mer repetitions and in plain text). Recently, heuristics were presented to compute a near-minimum such representation. We present an algorithm to compute a minimum representation in optimal (linear) time and use it to evaluate the existing heuristics. Our algorithm first constructs the de Bruijn graph in linear time and then uses a Eulerian-cycle-based algorithm to compute the minimum representation, in time linear in the size of the output.