title: Punch/Combine multiple strings into a single (shortest possible) string that includes all the chars of each strings in forward direction
body: <p>My purpose is to punch multiple strings into a single (shortest) string that will contain all the character of each string in a forward direction. The question is not specific to any language, but more into the <code>algorithm</code> part. (probably will implement it in a node server, so tagging <code>nodejs/javascript</code>).</p>
  
  <p>So, to explain the problem:</p>
  
  <p>Let's consider I have few strings</p>
  
  <pre><code>["jack", "apple", "maven", "hold", "solid", "mark", "moon", "poor", "spark", "live"]
  </code></pre>
  
  <p>The Resultant string should be something like:</p>
  
  <pre><code>"sjmachppoalidveonrk"
  </code></pre>
  
  <p>jack: s<strong>j</strong>m<strong>ac</strong>hppoalidveonr<strong>k</strong></p>
  
  <p>apple: sjm<strong>a</strong>ch<strong>pp</strong>oa<strong>l</strong>idv<strong>e</strong>onrk</p>
  
  <p>solid: <strong>s</strong>jmachpp<strong>o</strong>a<strong>lid</strong>veonrk</p>
  
  <p>====================================>>>> all in the forward direction</p>
  
  <p>These all are manual evaluation and the output may not 100% perfect in the example.</p>
  
  <p>So, the point is all the letters of each string have to exist in  the output in 
  <strong>FORWARD DIRECTION</strong> (here the actual problem belongs), and possibly the server will send the final strings and numbers like <code>27594</code> will be generated and passed to extract the token, in the required end. If I have to punch it in a minimal possible string it would have much easier (That case only unique chars are enough). But in this case there are some points:</p>
  
  <ol>
  <li><p>Letters can be present multiple time, though I have to reuse any
  letter if possible, eg: for <code>solid</code> and <code>hold</code> <code>o &gt; l &gt; d</code> can be
  reused as forward direction but for <code>apple</code> (<code>a &gt; p</code>) and <code>spark</code>
  (<code>p &gt; a</code>) we have to repeat <code>a</code> as in one case it appears before <code>p</code>
  for <code>apple</code>, and after <code>p</code> for <code>sparks</code> so either we need to repeat
  <code>a</code> or <code>p</code>. Even, we cannot do <code>p &gt; a &gt; p</code> as it will not cover both the case
  because we need two <code>p</code> after <code>a</code> for <code>apple</code></p></li>
  <li><p>We directly have no option to place a single <code>p</code> and use the same
  index twice in a time of extract, we need multiple <code>p</code> with no option
  left as the input string contains that</p></li>
  <li>I am (not) sure, that there is multiple outputs possible for a set of
  strings. but the concern is it should be minimal in length,
  the combination doesn't matter if its cover all the tokens in a forward direction. all (or one ) outputs of minimal possible length 
  need to trace.</li>
  <li>Adding this point as an <strong>EDIT</strong> to this post. After reading the comments and knowing that it's already an existing
  problem is known as  <a href="https://en.wikipedia.org/wiki/Shortest_common_supersequence_problem" rel="nofollow noreferrer">shortest common supersequence problem</a> we can
  define that the resultant string will be the shortest possible
  string from which we can re generate any input string by simply
  removing some (0 to N) chars, this is same as all inputs can be found in a forward direction in the resultant string.</li>
  </ol>
  
  <p>I have tried, by starting with an arbitrary string, and then made an analysis of next string and splitting all the letters, and place them accordingly, but after some times, it seems that current string letters can be placed in a better way, If the last string's (or a previous string's) letters were placed according to the current string. But again that string was analysed and placed based on something (multiple) what was processed, and placing something in the favor of something that is not processed seems difficult because to that we need to process that. Or might me maintaining a tree of all processed/unprocessed tree will help, building the building the final string? Any better way than it, it seems a brute force?</p>
  
  <p><strong>Note</strong>: I know there are a lot of other transformation possible, please try not to suggest anything else to use, we are doing a bit research on it.</p>