0

I have as input a list of n+2 continuous substrings of length 3. My goal is to find out whether there exists a string of length n such that all its continuous substrings of length 2 are exactly the input list that I have been given.

How can I efficiently solve this problem (e.g. for strings of length 4000)?

I have tried out a DP approach similiar to the one used for matrix chain multiplication but it didn't work.

Now I am thinking that I could convert this problem into a graph where the substrings are the vertices and two vertices (substrings of length 3) are connected by an edge if the substrings can be joined into a substring of length 4 (e.g. abc and bcd are connected as they can be joined into abcd). Would trying to find a Eulerian path in this graph solve my problem? Or am I completely wrong about all this?

julius
  • 1
  • 2
  • Did you mean 'contiguous'? Also, if your input list has only length-3 strings, how can a list of substrings of length-2 ever be exactly that input list? Some examples, and more details of what you've tried, would be useful. – kcsquared Mar 04 '22 at 21:53
  • Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. – Community Mar 05 '22 at 07:40

0 Answers0