Skip to main content
Talentd

Largest Odd Number in String - Solution & Explanation

EasyMathStringGreedy10 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

You are given a string num, representing a large integer. Return the largest-valued odd integer (as a string) that is a non-empty substring of num, or an empty string "" if no odd integer exists.

A substring is a contiguous sequence of characters within a string.

 

Example 1:

Input: num = "52"
Output: "5"
Explanation: The only non-empty substrings are "5", "2", and "52". "5" is the only odd number.

Example 2:

Input: num = "4206"
Output: ""
Explanation: There are no odd numbers in "4206".

Example 3:

Input: num = "35427"
Output: "35427"
Explanation: "35427" is already an odd number.

 

Constraints:

  • 1 <= num.length <= 105
  • num only consists of digits and does not contain any leading zeros.

Approach Overview

Problem Overview: You are given a numeric string num. The task is to return the largest-valued odd number that can be formed as a substring. Since substrings keep the original order of digits, the largest valid odd number must be a prefix that ends at the rightmost odd digit.

Approach 1: Checking Last Odd Digit (Greedy) (Time: O(n), Space: O(1))

This approach relies on a simple observation: an integer is odd if its last digit is odd (1, 3, 5, 7, 9). To maximize the value of the substring, you want the longest prefix that ends with an odd digit. Iterate from the end of the string toward the beginning and check each digit. As soon as you find an odd digit, return the substring from index 0 to that position inclusive. The scan takes at most n steps and no extra data structures are required, making it an efficient greedy strategy working directly on the string.

Approach 2: Using Regular Expression (Time: O(n), Space: O(n))

Regular expressions can also identify the longest prefix that ends with an odd digit. A pattern such as ^\d*[13579] matches any sequence of digits starting from the beginning of the string and ending with an odd digit. The regex engine scans the string until it finds the last valid odd-ending prefix. While the theoretical time complexity is still O(n), regex introduces additional overhead and temporary allocations compared with direct iteration. This approach is convenient in scripting languages like Python or JavaScript but less common in interviews where explicit math checks on digits are clearer.

Recommended for interviews: The greedy scan from the end is the expected solution. It demonstrates that you recognize the defining property of odd numbers and avoid unnecessary substring generation. Interviewers typically look for this observation and an O(n) pass with constant space. Regex solutions are concise but hide the underlying reasoning and are rarely preferred during whiteboard discussions.

Approach 1: Checking Last Odd Digit

If the entire string is considered as a whole number, you only need to check the last digit to determine if it's odd. This is because the entire substring from start to that odd digit will be the largest odd number available. If there is no odd digit, then there's no odd number in the string.

This function iterates from the end of the string, checking each digit to see if it is odd. Once it finds an odd digit, it marks the end of the string there and returns the substring from the start to that point.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1) because only a constant amount of space is used.

Try this approach in the editor →

Approach 2: Using Regular Expression

By utilizing regular expressions, find the largest substring ending in any odd digit directly. This will require reversing the string and searching for the first odd digit using a pattern.

This solution reverses the string and searches for the first occurrence of an odd digit using a regex pattern. Once found, it calculates the original position and slices the string accordingly.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n), mainly due to the string reversal and regex search.
Space Complexity: O(n) for the reversed string.

Try this approach in the editor →

Approach 3: Reverse Traversal

We can traverse the string from the end to the beginning, find the first odd number, and then return the substring from the beginning to this odd number. If there is no odd number, return an empty string.

The time complexity is O(n), where n is the length of the string num. Ignoring the space consumption of the answer string, the space complexity is O(1).

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Checking Last Odd Digit

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1) because only a constant amount of space is used.

Using Regular Expression

Time Complexity: O(n), mainly due to the string reversal and regex search.
Space Complexity: O(n) for the reversed string.

Reverse Traversal—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Checking Last Odd Digit (Greedy)O(n)O(1)Best general solution. Single scan from the end with minimal memory.
Regular Expression MatchO(n)O(n)Useful in scripting languages when concise pattern matching is preferred.

Video Solution

1. Largest Odd Number in String | Strings - Easy | #LearnDSA | Leetcode 1903 • Ayushi Sharma • 30,812 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Largest Odd Number in String easy or hard?
LeetCode classifies this problem as Easy. The challenge is recognizing that the largest odd substring must end at the rightmost odd digit. Once that observation is made, the implementation becomes a straightforward linear scan.
Largest Odd Number in String Python/Java solution
In both Python and Java, iterate from the end of the string and check if the current digit is odd using modulo or character comparison. Once an odd digit is found, return the prefix substring. Python typically uses slicing like num[:i+1], while Java uses substring(0, i+1).
How to solve Largest Odd Number in String in O(n)?
Traverse the string from the last index toward the beginning. Check each digit and stop when you encounter an odd digit (1, 3, 5, 7, or 9). Return the substring from index 0 to that position inclusive. If no odd digit exists, return an empty string. This guarantees a single linear pass.
What is the best approach for Largest Odd Number in String?
The optimal approach scans the string from right to left and finds the first odd digit. Once found, return the substring from the start of the string up to that index. This greedy strategy works because any longer substring ending with an even digit cannot be odd. The solution runs in O(n) time with O(1) extra space.
Is Largest Odd Number in String asked at Google/Amazon/Meta?
This problem style appears frequently in coding interviews that test string manipulation and basic math properties. Variants of prefix scanning and greedy digit checks have appeared in interviews at large tech companies including Amazon and Google-style interview rounds.
What data structure is used in Largest Odd Number in String?
The solution mainly operates on a string with simple index traversal. No complex data structures such as hash maps or stacks are required. The algorithm relies on checking digit parity and returning a substring.
What is the time complexity of Largest Odd Number in String?
The optimal solution runs in O(n) time where n is the length of the string. In the worst case you scan the entire string once to locate the rightmost odd digit. Space complexity is O(1) because only a few variables are used without additional data structures.

Ready to solve this problem?

Practice Largest Odd Number in String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Largest 3-Same-Digit Number in String