Longest Subsequence which is a Substring

For MTS role

You are given two strings x and y. You need to find the length of the longest subsequence of x that is also a substring of y.

A subsequence is a sequence derived from another string by deleting some or no elements without changing the order.

A substring is a contiguous part of a string.

Function Description

Complete the function longestSubsequenceWhichIsSubstring in the editor.

longestSubsequenceWhichIsSubstring has the following parameters:

1. String x: the first string
2. String y: the second string

Returns

int: the length of the longest subsequence of x that is also a substring of y

Approach

I generated all substrings of y and checked if they are subsequences of x.

Used a helper function for checking subsequence in O(M) time using two pointers.

Time complexity: O(N² * M), where N = len(y), M = len(x).