Shortest common SuperSequence
<p>The problem is that given 2 strings X and Y , we need to find length of the shortest sequence Z such that both the strings occur as sub sequence in Z. Now, I get the intuition that length = |X| + |Y| -|LCS(X,Y)|. But how do we prove it ?<br/></p>

<p>Ex: X = AGGTAB , Y = GXTXAYB , then Z = AGXGTXAYB and |Z| = 9 . LCS(X,Y) = GTAB</p>

<p>Reference : <a href="http://www.geeksforgeeks.org/shortest-common-supersequence/" rel="nofollow noreferrer">Link 1</a> <a href="https://en.wikipedia.org/wiki/Shortest_common_supersequence_problem" rel="nofollow noreferrer">Link 2</a></p>