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 algorithm
part. (probably will implement it in a node server, so tagging nodejs/javascript
).
So, to explain the problem:
Let's consider I have few strings
["jack", "apple", "maven", "hold", "solid", "mark", "moon", "poor", "spark", "live"]
The Resultant string should be something like:
"sjmachppoalidveonrk"
jack: sjmachppoalidveonrk
apple: sjmachppoalidveonrk
solid: sjmachppoalidveonrk
====================================>>>> all in the forward direction
These all are manual evaluation and the output may not 100% perfect in the example.
So, the point is all the letters of each string have to exist in the output in
FORWARD DIRECTION (here the actual problem belongs), and possibly the server will send the final strings and numbers like 27594
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:
Letters can be present multiple time, though I have to reuse any letter if possible, eg: for
solid
andhold
o > l > d
can be reused as forward direction but forapple
(a > p
) andspark
(p > a
) we have to repeata
as in one case it appears beforep
forapple
, and afterp
forsparks
so either we need to repeata
orp
. Even, we cannot dop > a > p
as it will not cover both the case because we need twop
aftera
forapple
We directly have no option to place a single
p
and use the same index twice in a time of extract, we need multiplep
with no option left as the input string contains that- 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.
- Adding this point as an EDIT to this post. After reading the comments and knowing that it's already an existing problem is known as shortest common supersequence problem 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.
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?
Note: 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.