How should I practice Longest Subsequence which is a Substring?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Salesforce online assessment problems in FastPrep.

Is Longest Subsequence which is a Substring associated with Salesforce?

FastPrep tags this as a Salesforce online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · String

Longest Subsequence which is a Substring

Learn this problem

● Hard

SalesforceFULLTIMEOA

See Salesforce hiring insights

Problem statement

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

longestSubsequenceWhichIsSubstring(x: String, y: String) → int

Complete the function longestSubsequenceWhichIsSubstring in the editor.

longestSubsequenceWhichIsSubstring has the following parameters:

String x: the first string
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).

Examples

Example 1

x = "abcd"y = "abdc"return = 3

The subsequence "abd" is present in x and also appears as a substring in y.

Example 2

x = "hackerranks"y = "hackers"return = 7

"hackers" is a substring of y and also a subsequence of x, so the answer is 7.

Constraints

1 <= x.length, y.length <= 2000
x and y contain lowercase English letters.