Longest Substring, Subarray or Subsequence: Window or DP?

As of 2026-10-19, TrueInterview's bank holds 49 candidate-reported longest-type coding questions from 17 big-tech companies. The word "longest" does not tell you the technique; contiguity does. A substring or subarray answer is contiguous and points to a sliding window or a running sum, while a subsequence answer is not and points to dynamic programming. If you are senior, make the base window automatic quickly and spend most of your time on its changed-constraint variants and string problems, because questions tagged dynamic-programming draw 16 of their 18 write-up links from junior, new-grad and intern candidates.

Disclosure: TrueInterview is an interview-preparation product and publishes this article. Facts about other products come from their public pages on the dates listed under Sources.

Must the answer be contiguous? Ask that before naming a technique

Ask it first, because contiguity splits this set more reliably than the wording of the prompt. Aman's AI Journal defines a subarray as "a contiguous slice of an array" and a substring as the same idea for strings. The same page defines a subsequence as "a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements".

That one distinction gives you a working rule. Use a variable sliding window when the answer is contiguous and validity survives shrinking: if a window has no repeated character, or at most k distinct characters, every window inside it does too, so moving the left edge always restores a broken window. Use Kadane's running sum when the answer is the best contiguous sum. Use DP when the answer may skip elements, as an increasing subsequence does.

Longest Palindromic Substring is the contiguous exception worth naming in the room. The string 'aba' is a palindrome but its inner window 'ab' is not, so shrinking does not restore validity, and the standard answer expands around each centre instead of sliding.

The tags come from the bank and a question can carry several; pairing each tag with titles is our reading of the titles, not data the bank stores.

Our take: the generic advice that longest problems are a DP topic overstates the case. DP is the largest single tag, but sliding-window, arrays and strings each sit close behind it, and the next section shows the window edging ahead of DP in phone screens. Learn one DP template for subsequences and spend the rest of your hours on windows and contiguous arrays.

Which longest-type questions do candidates report most?

Longest Substring Without Repeating Characters II leads, followed by Longest-Match Tokenizer, and six of the eight titles with at least three write-up links are contiguous by their titles. None of the eight has the word subsequence in its title. The table orders them by write-up links and adds the self-reported level split, which the senior section interprets.

These counts measure what candidates wrote up, not how often a company asks a question, and the questions are candidate-reported and reconstructed for practice rather than any company's official list. One write-up can link several questions, so the link column does not count distinct candidates.

The set is current: 39 of the 49 questions were last reported within the 12 months before 2026-10-19. By company, ByteDance has the most filed (11), then Google (10), Meta (9), Amazon (8) and Microsoft (7). Two of the top three titles are contiguous problems, so a candidate who can write a window from its invariant has covered the most-linked title and can spend the remaining hours on its variants.

Longest-Match Tokenizer needs a different tool, and its technique is our inference from the title: longest-match tokenization is usually done greedily, walking a trie of the vocabulary from each position and keeping the longest match. The bank's tries tag splits 8 senior-or-above to 2 junior-or-below links, the same split as this title's links. Read its statement before you commit to a trie, since the title alone does not fix the vocabulary format or the tie rules.

Why should phone-screen preparation start with the sliding window?

Because phone screens carry most of this set and the window leads there. Of the 49 questions, 34 were reported in phone screens, 14 in onsites and 7 in online assessments, and a question can appear in more than one round. Among the 34 phone-screen questions, sliding-window is the top tag (9), ahead of arrays (8), dynamic programming (7) and strings (6).

If your next round is a phone screen, that ordering is your schedule: windows first, contiguous arrays second, one DP template last. The window also has to be defended out loud, which is where most of the preparation time goes.

State the brute force, then stop

techinterview.org puts checking every substring for duplicates near O(n³), since there are about n²/2 substrings and each check can cost another n. techinterview.org also says an interviewer will usually let you state the brute force and then go quiet, and it treats that silence as the hint. Name the brute force in one sentence with its cost, then ask which work it repeats: every substring that starts one position later shares almost all of its characters with the last one.

Defend the window with its invariant

The invariant techinterview.org recommends is that "every character inside [left, right] is distinct". Its pointer argument is that each character enters the window once and leaves at most once, which caps total pointer movement at 2n. techinterview.org gives the result as O(n) time and O(min(n, k)) space, where k is the alphabet size.

Hello Interview's guide keeps the window as a dictionary of character counts. On a duplicate, the guide removes the leftmost character and decrements its count until only one copy remains. Its faster variant, the guide says, stores the index where each character last appeared, so the window contracts in one step instead of a while-loop. The same guide uses max() so the start never moves backward when the previous occurrence lies before the window.

Our take: write the count or set version first and offer the last-index version as the improvement. techinterview.org's argument is that "the set version is easier to defend because the invariant is right there in the loop". In a phone screen, a solution you can prove beats a faster one you have to patch.

A worked example from the bank

Take Longest Substring Without Repeating Characters II, the most-linked title, last reported in an Apple phone screen in 2026-09. The answer is contiguous, so name the technique family as a window before writing any code. Write the count version, state the invariant and the pointer bound, then switch to the last-index map and test it on 'abba'. The reports do not say what the "II" adds, so read the statement on the practice page and keep the follow-ups in the next section ready.

The base problem has its own report in the bank: an Amazon phone screen, last seen in 2026-09. techinterview.org says LeetCode 3 "turns up in phone screens at Amazon, Meta, Bloomberg, and a long tail of startups". Practise both versions on the same evening, since a twisted version is easiest to handle when the base window is automatic.

Which follow-ups turn the classic into the reported question?

The reported titles are mostly twisted classics, so prepare a ladder of follow-ups rather than one base solution. The most-linked title is a "II" version, and the dated variants in the bank change the validity condition, the edits allowed or the input itself. Each rung below keeps the window or the running sum and changes one rule.

• Return the substring, not the length. techinterview.org calls this a frequent next ask and solves it by saving the best left index and slicing at the end.
• At most k distinct characters. techinterview.org names LeetCode 340 as the generalisation and says getting there smoothly "is the signal that you learned the pattern rather than memorizing one answer".
• A different validity condition. Hello Interview's guide places Longest Repeating Character Replacement next in its sliding-window sequence. The window stays valid while its width minus the count of its most frequent character is at most k.
• One replacement on an array. Longest Non-Decreasing Subarray with One Replacement was reported in a Google phone screen in 2026-10, and TrueInterview lists it as medium. Precompute the non-decreasing run ending at each index and starting at each index, then try each replacement and join the neighbours when they fit.
• A bounded difference. Judging by its title, Uber's Longest Subarray with Bounded Diff keeps the window but makes the condition the gap between its largest and smallest element. Two monotonic deques, one for the maximum and one for the minimum, give each step amortised constant work.
• Several copies of the input. Maximum Subarray Sum After K Concatenations was reported in a Microsoft onsite in 2026-10. Run Kadane over two copies, then add the remaining copies' total only when the array's sum is positive.

Our take: rehearse at least two rungs for every base problem you practise. A candidate who restarts from a blank page when the condition changes looks as if the first answer was memorised, which is the impression techinterview.org warns about.

When is a longest problem really dynamic programming?

When the answer may skip elements. A window cannot help, because the best answer is not a range, and enumeration is hopeless: GeeksforGeeks counts 2^n - 1 non-empty subsequences for a sequence of size n, against n*(n+1)/2 non-empty subarrays for an array. Aman's AI Journal notes that generating every subsequence means generating the power set.

Two of the reported titles are subsequence problems. Finding the Longest Increasing Subsequence is filed under ByteDance, LinkedIn and Salesforce, and none of its write-up links comes from a senior-or-above candidate. Longest Subsequence of X That Is a Substring of Y was reported in a Salesforce OA in 2026-01. Judging by its title, it mixes both shapes: the part taken from X may skip characters while its match in Y must be contiguous, which points to a two-index DP.

For the increasing subsequence, write the quadratic DP first so the state is explicit, then offer the tails array with binary search. Say that the tails array gives the length, and that rebuilding the sequence needs parent pointers.

Our take: two DP problems are enough for this set if you are senior. Keep one clean increasing subsequence in both versions and one two-string DP, and stop there unless your target company's profile in the next section leans DP.

Which companies lean toward which technique?

The tag profiles differ enough to change your week. ByteDance's questions carry 5 sliding-window tags and no arrays tags, while Google's carry 5 arrays tags and no sliding-window tags. Meta leans window with 3 sliding-window tags, and Amazon and Microsoft each have 3 DP-tagged questions.

Apple's smaller set splits evenly, with 2 tags each for strings, sliding-window and two-pointers. Salesforce, Uber, Snapchat and Coinbase complete the top ten companies with 5, 3, 2 and 2 questions.

• ByteDance or Meta: add window variants, starting with Longest Repeating Character Replacement.
• Google: lean toward array problems such as the one-replacement subarray from the follow-up ladder.
• Amazon or Microsoft: keep the DP template warm, and for a Microsoft onsite add the concatenations problem.

The longest label also covers tree problems, and they need a different tool. Meta's Tree Diameter / Longest Path was reported in a phone screen in 2026-04, and Binary Tree Longest Consecutive Sequence II is filed under Uber, Google and Meta. Both are depth-first searches that return a length from each subtree, so practise them with your tree problems, not with windows.

What changes at senior and staff level?

Senior write-ups lean away from the base window and toward strings, and our reading is that senior candidates are expected to have the window down already. Write-ups link this set 32 times from candidates who reported a senior, staff-plus or manager level, and 47 times from junior, new-grad or intern candidates. Levels are what candidates stated on their own write-ups.

By tag, tries (8 vs 2), greedy (9 vs 4) and strings (18 vs 13) lean senior, while sliding-window (12 vs 18) and dynamic programming (2 vs 16) lean junior. Arrays (6 vs 7) and two-pointers (6 vs 6) are close to even. In the ranked table, Longest-Match Tokenizer and Longest Subarray with Bounded Diff are the titles that lean senior, Maximum Subarray has no senior links, and the most-linked title is close to even.

Our take: if you are senior or staff, cap subsequence DP at two problems and move the saved hours to the tokenizer, the bounded-difference window and one string-processing problem from your target company. The bank does not separate staff from senior here, so the staff guidance is our view: explain why the window is correct before you are asked, and adapt it to a new constraint without restarting. Per-title counts are small, so treat the split as a lean, not a rule.

Down-leveling note (our view): a coding round in this set rarely carries the level signal on its own; design depth, the project deep dive and behavioral scope do. What the coding round can do is cost you the floor, so a slow or patched window on a phone screen is the risk to remove first.

Where do candidates lose these rounds?

On mechanics, not on the idea. techinterview.org says the failure is almost never the big idea but the small mechanics. Each mechanic has a concrete check you can run before you say you are done, and most of them live in the window's bookkeeping rather than in the choice of technique.

• The width. techinterview.org flags writing right - left instead of the inclusive right - left + 1.
• The guard. In the last-index version, techinterview.org warns: "The entire game lives in the last[ch] >= left guard, and it is the line people drop under pressure."
• A stale index. Test 'abba': the final 'a' finds its old position behind the window, and without the guard the start moves backward and the window swallows a duplicate.
• The empty string. Hello Interview's guide expects 0 for an empty input.
• Case. Hello Interview's guide treats matching as case-sensitive and warns against assuming lowercase-only input.

Our take: write these checks as comments at the top of your file before every practice attempt. The generic advice is to learn more patterns, but techinterview.org's point is that the losses come from mechanics, and a checklist targets exactly those.

How we counted

Counts come from TrueInterview's question bank as of 2026-10-19 and cover the longest substring, subarray and subsequence coding questions described above. A question can be filed under several companies, reported in several rounds and tagged with several algorithm topics, so tallies overlap. Write-up links count candidate write-ups that point to a question, split by the level each candidate reported; the shape column and technique pairings are our reading of the titles.

FAQ

What is the difference between a substring, a subarray and a subsequence?

A subarray is a contiguous part of an array, as GeeksforGeeks defines it, and a substring is the same thing for a string. A subsequence may skip elements but keeps their order. Aman's AI Journal adds that a subset drops the order requirement too, and that every subarray is a subsequence and every subsequence a subset, but not the reverse. For interviews, the line that matters is contiguity, because it decides between a window and DP.

Is Longest Substring Without Repeating Characters a dynamic programming problem?

No. Hello Interview's guide solves it with a variable-length sliding window that returns the length of the longest valid window. You can phrase it as the longest valid substring ending at each index, but that recurrence collapses into the same window once you notice the start only moves forward. Present it as a window, defend the invariant, and keep DP for the subsequence problems in the bank.

How does binary search make longest increasing subsequence faster?

Keep a tails array in which each position holds the smallest tail of any increasing subsequence of that length. For each element, binary-search the first tail that is not smaller, replace it, or append when none exists. The array's length is the answer in O(n log n), against O(n²) for the table version. The tails array is not itself a valid subsequence, so rebuilding the answer needs parent pointers.

How do you avoid the brute force that enumerating every substring or subsequence implies?

State the brute force with its cost, then name the work it repeats. For contiguous answers, neighbouring windows share almost every element, so a sliding window or running sum reuses the previous answer. For subsequences, the best answer for a prefix feeds the next prefix, so DP stores it once. Saying which reuse applies is usually the moment the interviewer stops waiting and lets you code.

Which longest problems need a monotonic deque?

The ones where the window's validity depends on its largest or smallest element, such as a bound on the gap between them. Uber's Longest Subarray with Bounded Diff, judging by its title, is the reported example in this set. Keep one deque decreasing for the maximum and one increasing for the minimum, pop stale indices from the front as the left edge moves, and shrink while the gap exceeds the bound.

Do senior candidates get different longest-type questions than new grads?

Partly. In the self-reported level split, senior-or-above write-ups lean toward the tokenizer and string problems, while junior write-ups lean toward subsequence DP and Maximum Subarray. Both groups report the most-linked window title in similar numbers. If you are a new grad, the base window plus one DP template is a sensible start; if you are senior, add the changed-constraint variants and a string-processing problem.

Your practice plan

A three-week plan for someone working full time, at about an hour on most weekdays:

1. First week, the base window. Solve Longest Substring Without Repeating Characters II twice from a blank editor, once with a count map and once with a last-index map. Test both on an empty string, 'abba' and mixed-case input; TrueInterview says its coding questions are judged on hidden tests that show you the case you failed.
2. First week, the first rung. Solve Longest Repeating Character Replacement, then write the at-most-k-distinct generalisation from the same template.
3. Second week, contiguous arrays. Solve Maximum Subarray with Kadane, then Maximum Subarray Sum After K Concatenations.
4. Second week, changed constraints. Solve Longest Subarray with Bounded Diff with two deques, then Longest Non-Decreasing Subarray with One Replacement.
5. Third week, the DP cap. Solve Finding the Longest Increasing Subsequence in both versions and Longest Subsequence of X That Is a Substring of Y, and stop there unless your target leans DP.
6. Third week, senior-leaning strings. Solve Longest-Match Tokenizer and Longest Palindromic Substring, reading the tokenizer's statement in full before you choose a data structure.

Sources

• TrueInterview question bank — longest substring and subsequence at big-tech companies — counted 2026-10-19
• Aman's AI Journal • Distilled • Subarray vs. Substring vs. Subsequence vs. Subset — checked 2026-10-19
• How the sliding window solves Longest Substring Without Repeats – techinterview — checked 2026-10-19
• Longest Substring Without Repeating Characters | Hello Interview — checked 2026-10-19
• Real FAANG Interview Questions by Company · TrueInterview — checked 2026-10-19
• Subarrays, Subsequences, and Subsets in Array - GeeksforGeeks — checked 2026-10-19
• Interview prep compared: your application, end to end · TrueInterview — checked 2026-10-19

Last reviewed: 2026-10-19.