LeetCode #753: Cracking the Safe, De Bruijn Sequence via Hierholzer DFS

Brute to Best: every LeetCode problem, from the naive solution to the optimal one. In this video: The problem: a safe's password has n digits, each between 0 and k − 1, and the safe checks the last n digits you typed. Return the shortest string that contains every possible password. Brute force: try building strings and backtrack whenever you get stuck, which is exponential. The key insight: the answer is a De Bruijn sequence. Make each (n − 1)-digit string a node, so each password is an edge. An Euler circuit walks every edge exactly once. Run Hierholzer's DFS from the node of n − 1 zeros, writing down each edge digit in post-order. The answer has length kⁿ + n − 1. Dry run: with n = 2 and k = 2, the answer is 01100. It contains 01, 11, 10 and 00, each exactly once. Complexity: O(kⁿ) time and O(kⁿ) space. Problem: https://leetcode.com/problems/crackin... Related: Reconstruct Itinerary (332), Valid Arrangement of Pairs (2097), Gray Code (89) Full Brute to Best playlist on the channel. Subscribe for a new LeetCode problem, solved from brute force to the best solution, every day. Hashtags #leetcode #leetcode753 #crackingthesafe #debruijn #eulerianpath #hierholzer #dfs #graph #hard #coding #codinginterview #dsa #python #google #brutetobest