Find max word letter span
Company: Upstart
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a function that, given an input text string, computes the maximum word letter span and returns both
(a) the maximum span and
(b) the list of words that achieve that span. A word's letter span is the absolute distance between the first and last alphabetic letters in the word using positions a=0..z=25. Capitalization does not matter. Ignore punctuation and non-letter characters when determining the first and last letters. Words that begin and end with the same letter have span 0. The same two boundary letters yield the same span regardless of their order inside the word. Examples: "cab" -> 1, "pat" -> 4, "Float" -> 14, "wood" -> 19, "would" -> 19, "I" -> 0, "pop" -> 0; "can't" and "cannot." both have span 17. Return the maximum span and all words from the text that achieve it (state whether you return original surface forms or normalized forms). Analyze time and space complexity and explain how you handle ties, duplicates, contractions/hyphenations, and texts with no alphabetic words.
Quick Answer: This question evaluates proficiency in string processing, character mapping, and algorithmic analysis by requiring computation of per-word letter spans while accounting for case normalization, punctuation handling, ties, duplicates, and edge-case word forms.
Given an input text string, compute the maximum word letter span and return both (a) the maximum span and (b) the list of words that achieve that span.
A word's letter span is the absolute alphabetical distance between its first and last alphabetic letters, using positions a=0, b=1, ..., z=25. Capitalization does not matter, and non-letter characters (punctuation, digits, apostrophes in contractions, etc.) are ignored when finding the first and last letters of a word. Because we take the absolute value, the order of the two boundary letters does not change the span ("PAT" and "TAP" both have span 4). A word whose first and last alphabetic letters are the same has span 0.
Words are delimited by whitespace. Return the list of words in their original surface form (exactly as they appear in the text, including any surrounding punctuation), in order of appearance. Words containing no alphabetic characters at all do not participate. If the text has no alphabetic words, return a span of 0 and an empty list.
Return a pair [max_span, words].
Examples:
- "cab" -> 'c'..'b' = 1
- "pat" -> 'p'..'t' = 4
- "Float" -> 'f'..'t' = 14
- "wood" -> 'w'..'d' = 19
- "would" -> 'w'..'d' = 19
- "I" -> 0
- "pop" -> 0
- "can't" and "cannot." both have span 17 ('c'..'t').
Constraints
- 0 <= len(text) <= 10^5
- Words are separated by whitespace.
- Only ASCII letters a-z / A-Z count toward a word's first/last letter; all other characters are ignored when computing the span.
- Comparison is case-insensitive ('A' and 'a' map to the same position 0).
- If no word contains an alphabetic character, return [0, []].
Examples
Input: ("cab pat Float",)
Expected Output: [14, ["Float"]]
Explanation: Spans: cab=1, pat=4, Float=14 ('f'=5 to 't'=19). Maximum is 14, achieved only by Float.
Input: ("wood would",)
Expected Output: [19, ["wood", "would"]]
Explanation: Both go 'w'(22) to 'd'(3), span abs(22-3)=19. They tie, so both surface forms are returned in order.
Hints
- Split the text on whitespace, then for each token find its first and last alphabetic character, ignoring everything else.
- Map a letter to a number with ord(ch.lower()) - ord('a'); the span is abs(first - last), so order and case never matter.
- Keep a running maximum: start a fresh result list when you see a strictly larger span, and append to it on a tie. Skip tokens that contain no letters so all-punctuation/numeric tokens never affect the answer.