Substrings Without a Target Subsequence
Updated
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) → longExamples
Example 1
s = "abc"target = "ac"return = 5Only the substring "abc" contains "ac" as a subsequence. The other five non-empty substrings are valid.
Example 2
s = "aaaa"target = "aa"return = 4Every 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 = 6No substring contains "d", so all 3 * 4 / 2 = 6 non-empty substrings are valid.
Constraints
1 <= s.length, target.length <= 200000s.length * target.length <= 4 * 10^6sandtargetcontain only lowercase English letters.
More PhonePe interview questions
- Constrained Jump SequencesOA · Seen Aug 2026
- Maximum Payout with Context SwitchesOA · Seen Aug 2026
- Luna and the Colorful SocksOA · Seen Jul 2026
- Evaluate DivisionONSITE INTERVIEW · Seen Oct 2026
- K-th Smallest Value in a Sorted MatrixONSITE INTERVIEW · Seen Oct 2026
- Identify Two Failing Tests From an Oracle TranscriptONSITE INTERVIEW · Seen Sep 2026
- Count Bowl SubarraysONSITE INTERVIEW · Seen Jul 2026
- Reconstruct ItineraryONSITE INTERVIEW · Seen Jul 2026
Similar questions at other companies
- Maximum Equal-Bit Pairs in a SubsequenceAmazon · OA
- Longest Subsequence That Is a SubstringBooking.com · OA
- Count Digit Replacements with No Equal Adjacent DigitsMicrosoft · OAMicrosoft interview questions
- Palindrome CounterGoldman Sachs · OAGoldman Sachs interview questions
- Longest String ChainVisa · OAVisa interview questions
- Minimum-Cost Digit String DecodingSquadStack.ai · OA
- Maximum Redundancy After One Segment FlipBloomberg LP · OABloomberg LP interview questions
- Minimum Edit-Distance String for Each QueryTarget · OA
- Longest Subsequence That Is a SubstringWells Fargo · OAWells Fargo interview questions
- Non-Alternating Binary PartitionsThe D.E. Shaw Group · OAThe D.E. Shaw Group interview questions