Remove some substring from 𝑠 of maximum possible length such that after removing this substring t will remain a subsequence of 𝑠.

5 min readNov 14, 2019

Problem Statement

You are given a string s and a string t, both consisting only of lowercase Latin letters. It is guaranteed that t can be obtained from string s by removing some (possibly, zero) number of characters from s without changing the order of remaining characters (in other words, it is guaranteed that t is a subsequence of s).

For example, the strings “test”, “tst”, “tt”, “et” and “” are subsequences of the string “test”. But the strings “tset”, “se”, “contest” are not subsequences of the string “test”.

You want to remove some substring (contiguous subsequence) from s of maximum possible length such that after removing this substring t will remain a subsequence of s.

If you want to remove the substring s[l;r] then the string 𝑠s will be transformed to 𝑠(1) 𝑠(2) …𝑠(𝑙−1)𝑠(𝑟+1)𝑠(𝑟+2)…𝑠(|𝑠|−1)𝑠(|𝑠|)(where |s| is the length of s).

Your task is to find the maximum possible length of the substring you can remove so that string t is still a subsequence of string 𝑠.

Sample Cases

Input:
bbaba
bbOutput:
3Input:
baaba
abOutput:
2Input:
abcde
abcdeOutput:
0Input:
asdfasdf
fasdOutput:
3

Brute Force Approach

We can just iterate over all possible substrings and try to remove each of them. After removing the substring we can check if string 𝑡 remains the subsequence of string 𝑠 in linear time.

Time Complexity: O(n³)

Function: isSubSequence(string a, string b)
The function checks whether string a is a subsequence of string b.
Time complexity: O(n) where n is the size of the string b

Function that returns whether string “a” is a subsequence of string “b”.

Function: remove_maxlen(string a, string b)
The function returns the length of the maximum substring that can be removed from string b, so that string a is a subsequence of b.
Time complexity: O(n³) where n is the size of the string b

We’ll generate substring of all lengths and remove it. The max length of the substring that can be removed is max_len which is equal to size_of_s - size_of_t.

The function that returns the maximum substring that can be removed from a string s, such that t is still a subsequence of the remaining string of s.

Efficient Approach

NOTE:
s[i : j] denotes the substring of the string s from the index i to index j.
Also, we’ll be considering 0 based indexing.
Example: s = “abcdef” ; then s[1 : 3] = “bcd”

We can divide the solution into three parts.

First:

The substring to be removed is from some index to the end of the string s. So, t should be a subsequence of the string s[0 : index]

Second:

The substring to be removed is from starting to some index of the string s. So t should be a subsequence of the string s[index : s.size() - 1].

Third:

The string from index a to index b is removed. So the t should be a subsequence of “s[0 : a] + s[b : s.size()-1]” where b≥a.

The above-mentioned parts cover all the cases.

Implementation

Let’s understand how we’ll implement the above logic.

rightMost[i] : be such rightmost position x in the string s that the substring — t[i : t.size()-1] is the subsequence of s[x : s.size()-1].
leftMost[i]: be such leftmost position 𝑥 in string s that the substring 𝑡[0 : i] is the subsequence of 𝑠[0 : x].

First part:

let index = leftmost[t.size() - 1]

That means string t is a subsequence of s[0 : index], hence the substring from index +1 to the end of the string s can be removed.

s.size() - index- 1 is the max length of the substring that can be removed so that string t should be a subsequence of the string s[0 : index]
let fromLeft = s.size()-index-1

Second part:

Similarly, we’ll get the length of the maximum substring that can be removed from the start to some index, thereby making string t a subsequence of s[index : s.size()-1].

index is the max length of the substring that can be removed so that t should be a subsequence of the string s[index : s.size()-1].
let fromRight =index

Third part:

For any position i in string t, we can have string t as a subsequence of the string formed by “s[0 : leftmost[i]] + s[rightmost[i+1] : s.size()-1]”.

for i = 0 -> t.size()-1:
inbetween = max(inbetween, righmost[i+1] - leftmost[i] - 1)

The final ans[maximum substring length] will be the maximum of the values calculated in the above three parts
ans = max(fromLeft, fromRight, inBetween);