Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

## De Bruijn Sequence

Given a string (like ABCD), generate shortest String containing all combinations of the given string.

Example: For "AB", all combinations are {AA, AB, BA, BB}
One string containing all these combinations is AAABBABB.
But this is not the shortest.
Shortest string containing all combinations is AABBA
Such a string is called De Bruijn Sequence

Solution: Start with solution string containing 'n' characters, all set to the lowest character.
('n' is the length of the input string)

For the next character, choose highest character such that the string formed by the last n-1 characters of current
result and this character does not exist in the result.

If it does exist, choose the next highest character.

A java program to generate the DeBruijn Sequence is as follows:
 ```import java.util.Arrays; import java.util.LinkedHashSet; import java.util.Set; public class TextContainingAllCombinations { private static String generateDeBruijnSequence ( String s, Set combinations ) { char[] chars = s.toCharArray(); Arrays.sort(chars); // Start with all chars set to the shortest one String res = ""; for (int i=0; i=0; i--) { if (!combinations.contains(suffix + chars[i])) { res = res + chars[i]; combinations.add(suffix + chars[i]); break; } } //if (i>=chars.length) if (i<0) break; } return res; } public static void main (String args[]) { String s = "ABC"; Set combinations = new LinkedHashSet(); String res = generateDeBruijnSequence(s, combinations); System.out.println ("Result: " + res); System.out.println ("Result length: " + res.length()); System.out.println ("Combinations: "); for (String sub: combinations) { System.out.println (sub); } System.out.println ("No of combinations: " + combinations.size()); } } ``` Execution for "PQ" ```Result: PPQQP Result length: 5 Combinations: PP PQ QQ QP No of combinations: 4 ``` Execution for "ABC" ```Result: AAACCCBCCACBBCBACABCAABBBABAA Result length: 29 Combinations: CAB CAC CCA CCB CCC CAA ACC BBA ACB BBC BBB AAA AAC AAB CBA CBB BAC BAA ACA BAB CBC BCC ABC BCB ABB ABA BCA No of combinations: 27 ```

Order of execution: If N is the length of input string, then NN combinations are possible.
To make sure all of them are in the final output string, the outer loop will run NN times.
Also, there will be several failed comparisons on line 29 which will also be of order N.
So total order will be NN+1

Note the two commented lines on lines 26 and 37
The above algorithm works only if the next character chosen is the highest character possible.
If next lowest character is chosen, the algorithm stops very soon.

Example execution when lowest character is chosen:
```Result: AAABAACAA
Result length: 9
Combinations:
AAA
AAB
ABA
BAA
AAC
ACA
CAA
No of combinations: 7
```

### An example use of De-Bruijn Sequence

Consider a PIN-like code lock without an "enter" key which accepts the last n digits entered.
For example, a 4-digit digital ATM lock would have 104 solutions.
The De-Bruijn sequence can be used to shorten a brute-force attack on such a lock from 4x104 sequence to 104 + 4-1 string.

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

 Name: Email: (Your email is not shared with anybody) Comment: