How should I practice Substrings Without a Target Subsequence?

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

Is Substrings Without a Target Subsequence associated with PhonePe?

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

Problem · String

Substrings Without a Target Subsequence

Learn this problem

● Medium

PhonePeFULLTIMEOA

Problem statement

Given a string s and a non-empty string target, consider every non-empty contiguous substring of s.

A substring is invalid when target appears inside it as a subsequence: the characters of target occur in the same relative order, but they do not need to be adjacent. Count the substrings in which target does not appear as a subsequence.

Substrings with different start or end indices are counted separately, even when their text is identical.

Function

countValidSubstrings(s: String, target: String) → long

Examples

Example 1

s = "abc"target = "ac"return = 5

Only the substring "abc" contains "ac" as a subsequence. The other five non-empty substrings are valid.

Example 2

s = "aaaa"target = "aa"return = 4

Every substring of length at least 2 contains "aa" as a subsequence. The four one-character substrings are valid.

Example 3

s = "abc"target = "d"return = 6

No substring contains "d", so all 3 * 4 / 2 = 6 non-empty substrings are valid.

Constraints

1 <= s.length, target.length <= 200000
s.length * target.length <= 4 * 10^6
s and target contain only lowercase English letters.