# Shortest substring containing three short strings

• Given a long string `s` and short strings `t1`, `t2`, `t3` (which can have different length) find the shortest substring of `s` which contains `t1`, `t2` and `t3`.

Example:
`s = "abcdefghijklmnopqrst"`, `t1 = "abc"`, `t2 = "cde"`, `t3 = "klmn"`, return `"abcdefghijklmn"`;

• // Here is my C# solution

`````` struct found
{
public int loc;
public string str;
public found(int l, string s)
{
loc = l;
str = s;
}
}
public static void FindShortesSubstringWindow(string S, string t1, string t2, string t3)
{

System.Collections.Generic.Dictionary<string,int> tbl = new Dictionary<string,int> ();

System.Collections.Queue Q = new System.Collections.Queue();

int MinWindow = 0;
int MaxWindow = S.Length;
int MaxEnd = 0;

for (int i = 0; i < S.Length; i++)
{
if (i+t1.Length <= S.Length && S.Substring(i, t1.Length) == t1)
{
Q.Enqueue(new found(i, t1));
tbl[t1]++;
MaxEnd = (MaxEnd < i + t1.Length) ? i + t1.Length : MaxEnd;
}
if (i + t2.Length <= S.Length && S.Substring(i, t2.Length) == t2)
{
Q.Enqueue(new found(i, t2));
tbl[t2]++;
MaxEnd = (MaxEnd < i + t2.Length) ? i + t2.Length : MaxEnd;
}
if (i + t3.Length <= S.Length && S.Substring(i, t3.Length) == t3)
{
Q.Enqueue(new found(i, t3));
tbl[t3]++;
MaxEnd = (MaxEnd < i + t3.Length) ? i + t3.Length : MaxEnd;
}

if (tbl[t1] > 0 && tbl[t2] > 0 && tbl[t3] > 0) // all found so far
{
found f = (found) Q.Dequeue();
if (MaxEnd - f.loc < MaxWindow - MinWindow)
{
MinWindow = f.loc;
MaxWindow = MaxEnd;

}

tbl[f.str]--;

}

}

System.Console.WriteLine( S + "\n" + t1 + "\n" + t2 + "\n" + t3 + " \nMin Window : " + S.Substring(MinWindow, MaxWindow  - MinWindow ) + " \nStart at: " + MinWindow + " End at: " + MaxWindow );

}``````

• Here is my runnable code in Java.

``````public class SubString{

public String shortestSubString(String s, String t1, String t2, String t3){
if(s == null || t1 == null || t2 == null || t3 == null) return "";
int lengthT1 = t1.length(), lengthT2 = t2.length(), lengthT3 = t3.length();
if( lengthT1 > s.length() ||  lengthT2 > s.length() || lengthT3 > s.length()) return "";

int indexT1, indexT2, indexT3;

indexT1 = checkSubString(s, t1);
if(indexT1 != -1){
indexT2 = checkSubString(s, t2);
if(indexT2 != -1){
indexT3 = checkSubString(s, t3);
if(indexT3 != -1){
int startingIndex, finishingIndex;
startingIndex = Math.min(indexT1, Math.min(indexT2, indexT3));
finishingIndex = Math.max(indexT1 + lengthT1, Math.max(indexT2 + lengthT2, indexT3 + lengthT3));
return s.substring(startingIndex, finishingIndex);
}
}
}
return "";
}

private int checkSubString(String base, String a){

if(base == null || a == null || a.length() > base.length()) return -1;

int indexCurrent = 0, index = 0;

while(indexCurrent + index < base.length()){
if(base.charAt(indexCurrent + index) == a.charAt(index)){
if(index == a.length() - 1)
return indexCurrent;
index++;
}
else {
indexCurrent++;
index = 0;
}
}
return -1;
}

public static void main(String [] args){
String s, t1, t2, t3;
s = "abcdefghijklmnopqrst";
t1 = "abc";
t2 = "cde";
t3 = "klmn";

SubString sub = new SubString();
System.out.println(sub.shortestSubString(s, t1, t2, t3));
}

}``````

• Hi HabKar,

You code does not always give the shortest one. For example, given the input (t1)(t1)(t2)(t3)**** where * is arbitrary character. Your code give the substring (t1)****(t1)(t2)(t3) instead of the correct one (t1)(t2)(t3)

• This is an implementation http://channgo2203.github.io/strpuzzle1/

• Thanks for your feedback and post!

• ``````def shortestSubstring(s, t1, t2, t3):
# store all starting positions of three strings
que, dic = [], {}
length, start = len(s), -1
for i in range(len(s)):
for t in [t1, t2, t3]:
if s[i:i + len(t)] == t:
dic[t] = dic.get(t, 0) + 1
que.append((i, t))
while len(dic) == 3:
start, t = que[0]
if dic[t] == 1:
break
else:
que.pop(0)
dic[t] -= 1
if len(dic) == 3:
end = 0
for j, t in que:
end = max(end, j + len(t))
if end - que[0][0] < length:
start = que[0][0]
length = end - start
if start == -1:
return ''
return s[start:start + length]

print(shortestSubstring('abcdefghijklmnopqrst', 'abc', 'cde', 'klmn'))
print(shortestSubstring('abcdefghijklm', 'abc', 'cde', 'klmn'))
print(shortestSubstring('abcdefghijklm', 'abcde', 'cde', 'ab'))
``````

output:
abcdefghijklmn

abcde

I did not store max ends, so every time I need to go through que to find it. I guess I can improve on this by storing it.

• @HabKar I tested the case - s = "this is a test string this a"; t1 = "is"; t2 = "this"; t3 = "a";
The result is "this is a", however correct result should be "this a"

• I generated the below Java code to implementation it.

1. go though the all subString of base string from the end
2. get the every index of every short string in every subString
3. calculate the shortest substring.
``````public class ShortestSubstringContainingShortStrings {

public static String shortestSubString(String base, String...sub){

int matchStringLength = base.length();
String shortestSubString = "";
for( int i = base.length() - 1  ; i >= 0 ; i-- ){

System.out.println(i + " : " + base.substring(i) );
String subBase = base.substring(i);

int start = Integer.MAX_VALUE;
int end = -1;
int index = -1;

for( int j = 0 ; j < sub.length ; j++ ){
index = subBase.indexOf(sub[j]);
start = Math.min(start, index);
end = Math.max(end, index==-1 ? -1 : index+sub[j].length() );
System.out.println(sub[j] + "|" + index + " | " + start + " | " + end);
}

if( start == -1 ){
continue;
}

String matchString = subBase.substring(start, end);
System.out.println("*" + matchString);
if(  matchString.length() <= matchStringLength ){
matchStringLength = matchString.length();
shortestSubString = subBase.substring(start,end);
}
}

return shortestSubString;
}

}

// test case:		Assert.assertEquals("abcdefghijklmn",ShortestSubstringContainingShortStrings.shortestSubString("abcdefghijklmnopqrst", "abc", "cde", "klmn"));
Assert.assertEquals("this a",ShortestSubstringContainingShortStrings.shortestSubString("this is a test string this a", "is", "this" , "a"));

``````

• I've used KMP to find occurrences of each string:

``````class Ideone
{
public static String findShortest(String str , String[] patterns){
Integer minStart = null;
Integer minLength = null;

int[] j = new int[patterns.length];
Integer[] last = new Integer[patterns.length];
int[][] ff = new int[patterns.length][];

for(int  pattern = 0; pattern < patterns.length ; pattern++){
j[pattern] = 0;
last[pattern] = null;
ff[pattern] = failureFunction(patterns[pattern]);
}

for(int i = 0; i < str.length() ; i++){
for(int pattern = 0; pattern < patterns.length ; pattern++){
while(patterns[pattern].charAt(j[pattern]) != str.charAt(i)
&& j[pattern]!= 0 ){
j[pattern] = ff[pattern][j[pattern]];
}
if(patterns[pattern].charAt(j[pattern]) == str.charAt(i)){
j[pattern]++;
}
if(j[pattern] == patterns[pattern].length()){
j[pattern] = ff[pattern][j[pattern]-1];
last[pattern] = i-patterns[pattern].length() + 1;
int minS = last[pattern];
boolean valid = true;
for(int p2 = 0 ; p2 < patterns.length && valid; p2 ++){
if(last[p2] == null){
valid = false;
break;
}
minS = Math.min(minS,last[p2]);
}

if(valid){
int l = i - minS +1;
if(minLength == null || l < minLength){
minLength =  l;
minStart = minS;
}
}
}
}
}

if(minLength == null)
return null;
return str.substring(minStart,minStart+minLength);
}

public static int[] failureFunction(String str) {
int[] ff = new int[str.length()];
ff[0] = 0;

int j = 0;
int i = 1;

while(i < str.length()){
if(str.charAt(i) == str.charAt(j)){
ff[i] = j+1;
i++; j++;
} else {
if(j == 0){
ff[i] = 0;
i++;
} else {
j = ff[j-1];
}
}
}
return ff;
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.