Actually this problem is popular application of De Bruijn graphs.
Some idea about De Bruijn graph:
Let each node of De Bruijn graph consists of triplet $(XYZ)$. A directed arc can exists between one triplet say $(XYZ)$ to other triplet $(YZW)$ e.g there is an arc from node $(345)$ to $(459)$ since last $2$ – digits of first node is common to first $2$ – digits of second node.
Similary there is no arc from say $(245)$ to $(478)$. This way we create directed edges between nodes of De Bruijn graphs.
Properties of De Bruijn graphs:
- Each De Bruijn graphs has equal no of incoming & outgoing edges which in turn equals to no of symbols used for constructing triplets(in our case we have total $10$ digits using which we can construct triplets, hence no. of incoming edges (i.e. in – degree) = no. of outgoing edges (i.e. out – degree) $= 10$.
- Each De Bruijn graphs is Eulerian & Hamiltonian i.e Euler cycle & Hamiltonian cycle exists. So consider Euler cycle i.e. traversing each edge only once gives us minimum sequence. So we use this property to verify that sequence we got from this graph will always minimum so our solution will be always optimised.
Now lets solve our problem:
Since we have to find key which consists of is $4$ – digit, so we first create all triplet possible of the form $<XYZ>$. So total no. of such triplets $= 10*10*10 = 1000$.
Now we will start creating directed edge between nodes following the above condition we described in $1^{st}$ properties.
So for every two triplets of the form $<XYZ>$ & $<YZW>$, we create one edge which corresponds to sequence $XYZW$. So total no. of such sequence possible $= 10*10*10*10 = 10000$.
So upto this point we have successfully constructed De Bruijn graphs.
Now our solution is simple: Take any node say $<XYZ>$ and traverse to other node say $<YZW>$ this corresponds to sequence $XYZW$ i.e., for each encounter of edge in Euler path, we add one symbol to previous node. Here we added $W$ to $XYZ$. This way we traverse through Euler Path. Now since we have total $10000$ edges and for each edges, we are adding one character, so starting from any node say $<XYZ>$, we will have finally $3+10000 =10003$ characters in sequence.
And from the property of De Bruijn graphs, this sequence will be optimal.
In short, basically this algorithm work as follows:
Let correct key is $``\ 1234"$. We start with any triplet i.e., any node in graph say $012$. After that we read one more digit sequentially say we read $`2\textrm'$ i.e., traversing through edge which will take us to $``\ 122"$. So this traversal corresponds to $``\ 0122"$. Now we compare it with correct key, since no match, so we traverse further. Now say next char we read is $``\ 3"$, so it takes us to node $``\ 223"$ i.e., we reached at node $223$ from $122$. This gives us current sequence $``1223"$ & overall sequence $``\ 01223"$. We keep on traversing the graph till we get last $4$ – character of sequence as $``\ 1234"$. So in worst case we will get a sequence of length $``\ 10003"$.
