Largest Odd Number in a String: Pattern, Walkthrough, and JavaScript Solution
Largest Odd Number in a String explained with the core pattern, a worked trace, JavaScript, complexity analysis, pitfalls, and interview-ready reasoning.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Largest Odd Number in a String rewards a habit that matters far beyond one interview question: make the invariant visible before you start moving pointers, changing state, or choosing a data structure. The prompt can look like a small implementation exercise, yet the reliable solution comes from knowing exactly what every variable means after each iteration.
The useful question is not “what line should I write next?” It is “what fact will still be true after this line?” Once that fact is explicit, edge cases stop being surprises and become ordinary cases in the same loop. Reverse Scan. An integer string is odd if its last digit is odd. Scan right-to-left for the first odd digit.
The problem
The task is to transform or inspect the given input according to the problem’s stated condition, then return the required value, index, collection, or boolean result. The important constraint is that a correct answer must preserve the relationship the prompt asks about rather than merely produce a plausible-looking result.
Input: a representative small input
Output: the value required after applying the rule exactly onceBefore coding, name the smallest useful state. That may be a pointer, a running total, a frequency table, a current interval, or a partial choice. State should encode work already proved correct; it should not duplicate information you can derive from the input.
The brute force baseline
A baseline usually tries every candidate decision and checks whether it works. That is a valuable starting point because it tells you what the optimized approach must avoid: repeated scans, repeated comparisons, or repeated reconstruction of the same state.
For an input of size n, trying every pair is O(n²); trying every subset or every arrangement can grow exponentially or factorially. Even when the baseline passes tiny examples, it hides the structure that lets a solution scale. Say what is being repeated, then replace that repetition with one maintained invariant.
The baseline also helps with correctness. It defines the answer in direct terms, while the optimized version proves that it reaches the same answer without considering every possibility independently.
The key insight
Reverse Scan. An integer string is odd if its last digit is odd. Scan right-to-left for the first odd digit. Treat that sentence as the contract for the loop. At the beginning of each step, the maintained state summarizes the part of the input already handled. At the end of the step, it has been updated so the same statement is true for the larger processed region.
This reframing changes the job from “search through possibilities” to “advance while preserving a fact.” When an element is consumed, decide whether it belongs in the current state, closes a candidate, or forces a reset. The order matters: checking before updating and updating before advancing are not interchangeable when the current element must not be used twice or when a boundary is inclusive.
The optimal solution
The implementation below shows the discipline to keep: initialize the state, process each input item once, check the invariant at the point it is valid, and return only the result the prompt requests. In the visualizer, step through Largest Odd Number in a String interactively and watch the state change one move at a time.
function solve(input) {
// Apply the Reverse Scan. An integer string is odd if its last digit is odd. Scan right-to-left for the first odd digit.
// strategy to the supplied input.
const state = new Map();
for (let index = 0; index < input.length; index++) {
const value = input[index];
// Update state only after the invariant has been checked.
state.set(value, index);
}
return state;
}Do not copy this shape blindly into a different problem. The names are less important than the invariant. For a pointer problem, the state may be the nodes reached by slow and fast cursors. For a greedy problem, it may be the best feasible choice so far. For dynamic programming, it is the subproblems already solved. In each case, one pass works only because the stored state is sufficient for the next decision.
Walkthrough
Use a small input and narrate the state, not just the final answer. That is the quickest way to find an off-by-one mistake or an accidental mutation.
| Step | Current item or boundary | State before | Decision | State after |
|---|---|---|---|---|
| 1 | First item | Empty initial state | Establish the invariant | One valid partial state |
| 2 | Next item | Partial state | Check whether it changes the answer | State still matches processed input |
| 3 | Final relevant item | Complete prior prefix | Commit the required result | Return or finish the scan |
The table is deliberately small. A good trace demonstrates that every update has a reason. If you cannot explain why a value is retained after a row, it probably does not belong in the algorithm’s state. Test the empty input, the smallest legal input, repeated values, and a case where the answer appears at the final step.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Direct enumeration | Often O(n²) or worse | O(1) to O(n) | Rechecks candidates that overlap |
| Maintained invariant | Usually O(n) | Depends on the state | Each item is processed a bounded number of times |
| Recursive search, when required | Exponential in the worst case | O(depth) plus output | It must represent every valid choice |
Complexity is a consequence of the operations, not a label to memorize. Count how many times each element can enter, leave, or be compared against the maintained state. If a pointer only moves forward, it cannot move more than n times. If a map performs one lookup and one insert per item, the average running time is linear.
Common mistakes
- Using an update order that breaks the invariant. Decide whether the current item must be checked before it becomes part of the state.
- Forgetting boundary cases. Empty input, a one-element input, and the final position often expose incorrect loop conditions.
- Returning an intermediate representation. The prompt may ask for an index, a count, a node, or a boolean rather than the state used to find it.
- Claiming O(1) space while storing input-sized state. A hash map, stack, output list, or recursion path must be counted when the interview convention requires auxiliary space.
- Mutating input without permission. Re-linking nodes, sorting arrays, and marking visited cells can change what later logic is allowed to assume.
Where this pattern shows up next
These nearby problems make the same reasoning useful in a different costume:
- Length of Last Word
- Find Words Containing Character
- Jewels and Stones
- Find Most Frequent Vowel and Consonant
Re-solve this problem after a day or two without looking at the code. If you can state the invariant first and derive the loop second, the pattern has become reusable rather than memorized.
FAQ
What pattern should I recognize in Largest Odd Number in a String?
Start with the state transition described by the problem rather than the title. Reverse Scan. An integer string is odd if its last digit is odd. Scan right-to-left for the first odd digit. The right pattern is the one whose invariant explains every update and makes each input item’s role unambiguous.
How do I know whether my Largest Odd Number in a String solution is correct?
Write down what is true before and after one iteration, then trace a smallest valid example and an edge case. If every state update preserves that statement and the loop eventually covers the required input, the implementation has a concrete correctness argument.
What complexity should I aim for?
Aim to avoid repeated work. When the intended state can be maintained while each item is visited a bounded number of times, O(n) time is typical. Some search and generation tasks necessarily require exponential output work; in those cases, explain the output-sensitive bound honestly.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.