Find longest subsequence of x that is a substring of y

Q: Find longest subsequence of x that is a substring of y

This is a Coding & Algorithms interview question from Salesforce for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Given two strings x and y, compute the maximum length of a string s such that:

s is a subsequence of x (can delete zero or more characters from x without reordering the remaining characters), and
s is a substring of y (must appear as a contiguous block in y ).

Return the maximum possible length.

Example

x = "abcd" , y = "abdc"
- One optimal choice is "abd" (subsequence of x , substring of y ), so the answer is 3 .

Sample

x = "hackerranks" , y = "hackers"
- Output: 7 (because "hackers" is a subsequence of x and also a substring of y ).

Find longest subsequence of x that is a substring of y

Example

Sample

Comments (0)