Most Relevant Text Span
Reported by candidates from Hebbia's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The Hebbia OA reported in April 2025 looks like a string problem, but the string is a decoy. The whole thing hinges on a running sum, not on any fancy data structure: one integer carried across the array. It's Kadane's algorithm wearing a text costume, with a tie-break rule that trips people up. Max-relevance span, earliest start, then shortest. If you blank on the tie-break logic under the clock, StealthCoder is the safety net running invisibly during the live OA. Know the trick first, though. It's about 15 lines.
The problem
You are given a nonempty lowercase string text and an integer array scores of the same length. The relevance of a nonempty contiguous span is the sum of the scores aligned with its characters. Return the substring with the largest relevance. If several spans have the same largest relevance, return the one with the earliest starting index. If they also have the same starting index, return the shortest one. Function mostRelevantSpan(text: String, scores: int[]) → String Examples Example 1 text = "search" scores = [-2,4,3,-5,2,1] return = "ea" The span "ea" has relevance 4 + 3 = 7, which is the largest possible sum. Example 2 text = "matrix" scores = [-4,-2,-7,-1,-5,-3] return = "r" Every score is negative. The single character "r" has score -1, the largest available relevance. Example 3 text = "abcd" scores = [1,-1,1,-1] return = "a" Several spans have relevance 1. The earliest starts at index 0, and "a" is the shortest span with that start and score. Constraints 1 ≤ text.length = scores.length ≤ 2 * 10^5. text contains only lowercase English letters. -10^9 ≤ scores[i] ≤ 10^9.
Reported by candidates. Source: FastPrep
Pattern and pitfall
This is maximum subarray with index tracking. Walk the array, keep a current sum and its start index. If the current sum before adding scores[i] is not positive, restart at i. Otherwise extend. Compare each candidate span to the best: higher sum wins, equal sum wins only if the start is earlier, and with the same start the shorter end wins. Use 64-bit integers, since sums reach 2 * 10^5 * 10^9. The pitfall is the restart rule. Restarting on a sum of zero (not just negative) changes which start index you report, and extending through a zero prefix gives an earlier start. Since earliest start wins ties, extend when the sum is zero, restart only when it's strictly negative. All-negative input must still return the single largest element. Return text.substring(start, end+1). If the tie-break gets tangled live, StealthCoder can hand you the clean version.
The honest play: practice the pattern, and have StealthCoder ready for the one you didn't see coming.
You can drill Most Relevant Text Span cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built for the candidate who saw this exact problem leak two days before his OA and wondered if anyone had a play.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Hebbia's OA.
Hebbia reuses patterns across OAs. Built for the candidate who saw this exact problem leak two days before his OA and wondered if anyone had a play. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Most Relevant Text Span FAQ
What's the trick in Most Relevant Text Span?+
It's Kadane's algorithm on the scores array, with start and end indices tracked. The text is only used at the end to slice the answer. Linear time, constant extra space. The real work is getting the tie-break rules right, not the core sum logic.
How do the tie-breaks work?+
Highest sum first. On equal sums, pick the earliest start index. On equal sum and equal start, pick the shortest span. So when you compare a new candidate, only replace the best if the sum is strictly greater, or equal with a smaller start, or equal with the same start and a shorter length.
Why do I need 64-bit integers?+
Scores go up to 10^9 in magnitude and the string can be 2 * 10^5 long. A full-span sum can reach 2 * 10^14, which overflows a 32-bit int. Use long in Java or C++. Python handles it automatically.
Should I reset the running sum at zero or below zero?+
Reset only when the running sum is strictly negative. A zero-sum prefix doesn't hurt the total, and keeping it preserves an earlier start index, which the tie-break prefers. Resetting at zero can return a later start than the expected answer.
How do I prepare for this in 48 hours?+
Code Kadane's from scratch twice, once returning the sum and once returning indices. Then add the tie-break rules and test the three examples, especially the all-negative one. Also test a case with zeros in the middle. That covers nearly every bug in this problem.