Largest Odd Number in a String
WHAT IT SAYS
Given a string of digits with no leading zeros, return the largest-valued odd number that appears as a substring, or an empty string if there is none.
WHAT IT'S REALLY ASKING
"You are picking substrings but comparing them as NUMBERS — and with no leading zeros, a longer number beats a shorter one before a single digit is ever compared. So you want the longest substring you can get, which means starting at index 0 and reaching as far right as possible. The only thing that can stop you is the last digit."
Generate every substring and compare
O(n^2) substrings, each costing up to O(n) to build and compareEnumerate all n(n+1)/2 substrings, keep the ones ending in an odd digit, and compare them as big integers to find the largest.
WHERE THE WORK IS WASTED — Almost every substring you generate is dominated by another substring you also generate. Any substring s[i..j] with i greater than 0 sits inside s[0..j], which has the same last digit (so it is odd if and only if the other one is) and strictly more digits (so it is strictly larger). You are building quadratically many candidates when all but n of them were beaten at birth.
Length beats digits; only the last digit can disqualify you.
Two facts collide, and between them they leave exactly one candidate standing. First: with no leading zeros anywhere in the input, more digits means strictly bigger. A 5-digit number beats a 4-digit number without a single digit comparison — the comparison never even gets a chance to run. So VALUE is dominated by LENGTH. Second: a number is odd if and only if its last digit is odd. Nothing about the front of the substring, nothing about its interior, nothing about its length affects that. So VALIDITY is dominated by the LAST character. Put them together. Every odd substring ends at some odd digit. Among all of them, the longest possible one ends at the RIGHTMOST odd digit — because any odd substring ending further left is strictly shorter, and there is nothing further right to end at. And the longest substring ending at that position is the one that starts at index 0. So the answer is not merely 'probably a prefix'. It is forced to be a prefix, and the only remaining decision is where it stops. Walk in from the right until you find an odd digit, and cut there.
Scan right to left, cut at the first odd digit
O(n) time, O(1) extra space — one pass, one substring built at the very endWalk from the last character towards the first. The moment you meet an odd digit at index i, return s[0..i] and stop. If you fall off the left edge without finding one, every substring is even and the answer is the empty string.
Longest Wins, So Only the End Matters
YOU'LL SEE IT AGAIN WHEN
- You are choosing a substring but the objective is numeric or lexicographic in a way where LENGTH dominates — which collapses the search from 'which substring' to 'how far can I extend'.
- The validity condition depends on only ONE position of the candidate (its last digit, its parity, its first bit), so scanning from that end answers it directly.
- The naive solution enumerates candidates that are provably dominated by other candidates it also enumerates.