Problem 95. Given two strings, find the maximum overlap

Created by Cody Team

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Given two strings s1 and s2, create a new string s3 which is as short as possible and contains both strings.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>If</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ s1 = [1 2 3 4 5]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>and</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ s2 = [5 4 3 2]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>then</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ s3 = [1 2 3 4 5 4 3 2]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>There is guaranteed to be one best solution.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

1774 Solutions
560 Solvers

Last Solution submitted on Jul 29, 2021

Last 200 Solutions

Problem Comments

10 Comments

10 Comments

Show 7 older comments

David Young on 8 Feb 2012

This would be improved by a richer test set to avoid solutions based on simple lookup of the test cases.

I think we can assume the entries are all positive integers, but it would be good if that was stated in the problem specification.

Aurelien Queffurust on 29 Jun 2012

Definetely agree. Adding more tests in the test suite and rescoring the solutions will elmiminate solution under a score of 92

Richard Zapor on 6 Jul 2012

My 33 is a terrible solution. Please add more test cases.
Tim's 80 is very good and my 83 is also valid. Addition of a common random value at an end overlap will eliminate chicanery. v=randi(100) [1 2 3 v] [v 4 5].

Richard Zapor on 6 Jul 2012

Created legitimate size 72.

Ned Gulley on 6 Jul 2012

Added a few more tests. Thanks for the comments!

Luigi Sanguigno on 28 Oct 2012

s1 = [3 1 4 1 5 9 2 6 5 3 5];
s2 = [9 2 6 5];
s3_correct = [3 1 4 1 5 9 2 6 5 3 5]; maybe is not correct ;-)

Michael Eldredge on 13 Feb 2018

Problems 1 and 2 have alternate solutions:

1) [5 4 3 1 2 3 4 5]
2) [1 0 1 7 7 7 6 0 1]

Sanzhar Askaruly on 21 Aug 2019

Did I just solved this myself? Toughest for me so far. Thanks!!!

Bryan Lambo on 8 Jan 2020

This did not make me sleep. Most difficult so far, took me some few hours lol.

Shlomo Geva on 17 Nov 2020

minor point - the specification is poorly worded.
The test input/output is not strings, but rather integer arrays.
e.g.
s1 = [10 20 30 40 50]
rather than "10 20 30 40 50"

I suppose this problem was written before the introduction of strings to Matlab (2016b) and so it may not have been so ambiguous at the time. (although even back then I would have interpreted the word "string" to mean a character array.)

Solution Comments

Solution 1400364

1 Comment

1 Comment

Shlomo Geva on 17 Nov 2020

Nice, but misses an edge case, hence not quite correct. It will enter an infinite recursion loop when the two inputs, s1 and s2, are disjoint (i.e. they do not overlap).
Easy to fix with a check that intersect(s1,s2) is not empty.

Solution 1182647

2 Comments

2 Comments

han gao on 1 Jan 2018

can't understand

Alex on 19 Jun 2020

Try this with: [ 1 2 3], [3 1 2]
Finds: [1 2 3 1 2]
Should find: [3 1 2 3]

Solution 1135848

1 Comment

1 Comment

Shlomo Geva on 17 Nov 2020

The solution is not correct.
It hard codes a test case that it cannot pass otherwise.
There are other cases that it cannot solve, although not in the test set.

Solution 49798

1 Comment

1 Comment

shen on 15 Dec 2013

hello, have you ever tried s1 = [ 1 2 3 ], s2= [1 2]?

Solution 33563

2 Comments

2 Comments

blaat on 11 Feb 2012

Nice :) I was trying to think of clever ways to use convolution, but didn't manage. This should be the leading solution instead of the lookup based on the test cases..

Aurelien Queffurust on 11 Jul 2012

well commneted

Solution 9598

1 Comment

1 Comment

Peter Wittenberg on 25 May 2012

Come on. Put in a general solution rather than gaming the solution set.

Problem Recent Solvers560

Problem Tags

matlab

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 95. Given two strings, find the maximum overlap

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers560

Suggested Problems

More from this Author95

Problem Tags

Community Treasure Hunt

Problem 95. Given two strings, find the maximum overlap

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers560

Suggested Problems

More from this Author95

Problem Tags

Community Treasure Hunt

Players