You are given a sequence of letters $x_{1}, x_{2} \dots x_{n}$ where each $x_{i} \in \left \{ a, b, c, d, e, f, g, h \right \}$. You can form a new sequence from the given sequence as follows. Start with $x_{1}$. Place $x_{m+1}$ either to the left or to the right of the sequence already built from $x_{1}, x_{2} \dots x_{m}$.
For instance, from $dcbeb$ you can form $ecdbb$ through the steps $d \rightarrow cd \rightarrow cdb\rightarrow ecdb\rightarrow ecdbb$ and $bbcde$ through the steps $d \rightarrow cd \rightarrow bcd\rightarrow bcde\rightarrow bbcde$.
What is the largest sequence in lexicographic (dictionary) order that you can form from the input sequence $becgdfg?$
-
$ggebcdf$
-
$ggfedcb$
-
$ggecbdf$
-
$ggfebcd$
