FastPrepSubstrings Without a Target Subsequence
Problems/Substrings Without a Target Subsequence

Substrings Without a Target Subsequence

PhonePe logoPhonePe● MediumFULLTIMEOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a PhonePe online assessment. The report does not give the alphabet or the size limits. Our version is about 97% the same as the reported question.

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.

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
All PhonePe interview questionsSee PhonePe hiring insights
Saved
class Solution {
    public long countValidSubstrings(String s, String target) {
      // write your code here
    }

}
Checking account…