How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during HR Screen rounds at Salesforce.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Salesforce during technical interviews.

Find longest subsequence of x that is a substring of y

Company: Salesforce

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: HR Screen

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`).

Quick Answer: This question evaluates string-algorithm skills and conceptual understanding of subsequences versus substrings, along with attention to algorithmic efficiency when relating non-contiguous selections to contiguous patterns.

Given two strings `x` and `y`, compute the **maximum length** of a string `s` such that: - `s` is a **subsequence** of `x` (you may delete zero or more characters from `x` without reordering the remaining characters), and - `s` is a **substring** of `y` (it must appear as a contiguous block in `y`). Return the maximum possible length. ### Example - `x = "abcd"`, `y = "abdc"` → answer `3`. One optimal choice is `"abd"`, which is a subsequence of `x` and a contiguous substring of `y`. ### Sample - `x = "hackerranks"`, `y = "hackers"` → answer `7`, because `"hackers"` is a subsequence of `x` and also a substring of `y`. **Approach.** Every candidate `s` is a contiguous substring `y[i..j]` of `y`. So enumerate substrings of `y` and keep the longest one that is also a subsequence of `x`. Checking whether a string `t` is a subsequence of `x` is a single left-to-right two-pointer scan of `x`. A useful pruning fact: if `y[i..j]` is NOT a subsequence of `x`, then no longer substring starting at the same `i` can be either, so you can stop extending that start index.

Constraints

0 <= len(x), len(y)
Strings consist of printable characters (typically lowercase English letters in the examples).
The answer is 0 when no character of y appears in x, or when either string is empty.
The result never exceeds min(len(x), len(y)).

Examples

Input: ("abcd", "abdc")

Expected Output: 3

Explanation: "abd" is a subsequence of x="abcd" and a substring of y="abdc", length 3. No length-4 substring of y is a subsequence of x.

Input: ("hackerranks", "hackers")

Expected Output: 7

Explanation: The whole of y="hackers" is a subsequence of x="hackerranks" (drop the extra r, n, s), so the answer is its full length 7.

Input: ("", "abc")

Expected Output: 0

Explanation: x is empty, so the only common string is the empty string; length 0.

Input: ("abc", "")

Expected Output: 0

Explanation: y is empty, so there is no non-empty substring of y; length 0.

Input: ("aaaa", "aa")

Expected Output: 2

Explanation: y="aa" is a subsequence of x="aaaa", so the whole substring of length 2 qualifies.

Input: ("abc", "xyz")

Expected Output: 0

Explanation: x and y share no characters, so no non-empty substring of y is a subsequence of x; length 0.

Input: ("abcabc", "abcabc")

Expected Output: 6

Explanation: y equals x, and any string is a subsequence of itself, so the whole length-6 substring qualifies.

Input: ("a", "a")

Expected Output: 1

Explanation: Single matching character; the substring "a" of y is a subsequence of x, length 1.

Hints

Every valid s is a contiguous substring of y. Enumerate substrings y[i..j] and test each against x.
Testing whether a string t is a subsequence of x is a single two-pointer pass: walk through x once, advancing a pointer in t whenever characters match; t is a subsequence iff the pointer reaches the end of t.
Pruning: if y[i..j] is not a subsequence of x, then no longer substring starting at i can be either — break out of the inner loop. Also skip any candidate whose length is not greater than the best found so far.

Quick Overview

This question evaluates string-algorithm skills and conceptual understanding of subsequences versus substrings, along with attention to algorithmic efficiency when relating non-contiguous selections to contiguous patterns.