- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Suppose we have a string s and another string t. And t is a subsequence of s. We have to find the maximum length of a substring that we can remove from s so that, t is still a subsequence of s.

So, if the input is like s = "xyzxyxz" t = "yz", then the output will be 4, as We can remove the substring "abca"

To solve this, we will follow these steps −

left := a new list, right := also a new list

c1 := -1, c2 := -1, c3 := -1

j := 0

for i in range 0 to size of s, do

if s[i] is same as t[j], then

insert i at the end of left

j := j + 1

if j is same as size of t , then

c1 := size of s - i - 1

come out from the loop

j := size of t - 1

for i in range size of s - 1 to 0, decrease by 1, do

if s[i] is same as t[j], then

insert i into right at position 0

j := j - 1

if j is same as -1, then

c2 := i

come out from the loop

for i in range 0 to size of t - 1, do

c3 := maximum of c3 and (right[i + 1] - left[i] - 1)

return maximum of c1, c2 and c3

Let us see the following implementation to get a better understanding −

class Solution: def solve(self, s, t): left = [] right = [] c1 = -1 c2 = -1 c3 = -1 j = 0 for i in range(len(s)): if s[i] == t[j]: left.append(i) j += 1 if j == len(t): c1 = len(s) - i - 1 break j = len(t) - 1 for i in range(len(s) - 1, -1, -1): if s[i] == t[j]: right.insert(0, i) j -= 1 if j == -1: c2 = i break for i in range(len(t) - 1): c3 = max(c3, right[i + 1] - left[i] - 1) return max(c1, c2, c3) ob = Solution() s = "xyzxyxz" t = "yz" print(ob.solve(s, t))

"xyzxyxz", "yz"

4

- Related Questions & Answers
- Program to find length of longest balanced subsequence in Python
- Program to find length of longest anagram subsequence in Python
- Program to find length of longest increasing subsequence in Python
- Program to find length of longest palindromic subsequence in Python
- Program to find length of longest circular increasing subsequence in python
- Program to find length of longest common subsequence in C++
- Program to find length of longest bitonic subsequence in C++
- Program to find length of longest common subsequence of three strings in Python
- Program to find out the length of longest palindromic subsequence using Python
- Program to find length of longest arithmetic subsequence of a given list in Python
- Program to find length of longest Fibonacci subsequence from a given list in Python
- Program to find length of longest alternating subsequence from a given list in Python
- Program to find length of longest sign alternating subsequence from a list of numbers in Python
- Program to find number of subsequence that are present inside word list in python
- Length of Longest Fibonacci Subsequence in C++

Advertisements