# Tag Info

You can solve this using dynamic programming. I will describe it in terms of constructing a graph and finding shortest paths in the graph, which is roughly equivalent. Let $A[1..n]$ be the input string you are trying to encode. Let's construct a graph where each vertex is identified by an integer $i$, with $i \in \{0,1,2,\dots,n\}$. Each edge will have both ...