Mật khẩu là chuỗi độ dài n trên ký tự 0..k-1. Hộp kiểm tra n ký tự cuối nhập vào. Tìm chuỗi ngắn nhất chắc chắn chứa mọi mật khẩu khả dĩ (chuỗi de Bruijn).
Ví dụ
n=2, k=2 → "01100" (các cặp: 00,01,11,10,00).
Thuật toán Hierholzer (Eulerian path)
Xây đồ thị: đỉnh = chuỗi độ dài n-1, cạnh = thêm 1 ký tự. Tìm chu trình Euler. Dùng DFS lùi (post-order) xây kết quả.
Chương trình C++
#include <bits/stdc++.h>
using namespace std;
class Solution {
unordered_set<string> visited;
string ret;
void dfs(string s, int k) {
for(int i=0; i