Largest Odd Number in String solution and explanation
Google
9 more videos on this problem
1. Largest Odd Number in String | Strings - Easy | #LearnDSA | Leetcode 1903Ayushi Sharma · 9:23 · 30K views
Largest Odd Number in String | Amazon | Leetcode 1903codestorywithMIK · 9:10 · 19K views
Largest Odd Number in String - Leetcode 1903 - PythonNeetCodeIO · 5:49 · 11K views
LeetCode 1903. Largest Odd Number in String - Interview Prep Ep 122Fisher Coder · 7:07 · 3K views
Largest Odd Number in String - LeetCode #1903 - Python, JavaScript, Java and C++CodingNinja · 1:47 · 2K views
Largest Odd Number in String - Leetcode 1903Algorial · 3:36 · 2K views
Solving LeetCode 1903 Largest Odd Number in String | Math | Greedy | Amazon | Adobe | EasyCode Harmony · 4:36 · 1K views
1903. Largest Odd Number in String (Leetcode Easy)Programming Live with Larry · 4:51 · 544 views
1903. Largest Odd Number in String | HINDI EXPLANATION | LEETCODE | TUTORIAL - 43Coding Kart · 10:37 · 312 views
1903. Largest Odd Number in String - LeetCode JavascriptBecoming A Better Dev (with David) · 7:12 · 298 views
The problem
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 <= 105numonly 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.
def largestOddNumber(num: str) -> str:
for i in range(len(num) - 1, -1, -1):
if int(num[i]) % 2 != 0:
return num[:i + 1]
return ""
print(largestOddNumber("52"))
print(largestOddNumber("4206"))
print(largestOddNumber("35427"))public class LargestOddNumber {
public static String largestOddNumber(String num) {
for (int i = num.length() - 1; i >= 0; i--) {
if ((num.charAt(i) - '0') % 2 != 0) {
return num.substring(0, i + 1);
}
}
return "";
}
public static void main(String[] args) {
System.out.println(largestOddNumber("52"));
System.out.println(largestOddNumber("4206"));
System.out.println(largestOddNumber("35427"));
}
}#include <iostream>
#include <string>
std::string largestOddNumber(std::string num) {
for (int i = num.size() - 1; i >= 0; --i) {
if ((num[i] - '0') % 2 != 0) {
return num.substr(0, i + 1);
}
}
return "";
}
int main() {
std::cout << largestOddNumber("52") << std::endl;
std::cout << largestOddNumber("4206") << std::endl;
std::cout << largestOddNumber("35427") << std::endl;
return 0;
}function largestOddNumber(num) {
for (let i = num.length - 1; i >= 0; i--) {
if (parseInt(num[i]) % 2 !== 0) {
return num.slice(0, i + 1);
}
}
return "";
}
console.log(largestOddNumber("52"));
console.log(largestOddNumber("4206"));
console.log(largestOddNumber("35427"));#include <stdio.h>
#include <string.h>
char* largestOddNumber(char *num) {
int length = strlen(num);
for (int i = length - 1; i >= 0; i--) {
if ((num[i] - '0') % 2 != 0) {
num[i + 1] = '\0';
return num;
}
}
return "";
}
int main() {
printf("%s\n", largestOddNumber("52"));
printf("%s\n", largestOddNumber("4206"));
printf("%s\n", largestOddNumber("35427"));
return 0;
}using System;
public class LargestOddNumber {
public static string largestOddNumber(string num) {
for (int i = num.Length - 1; i >= 0; i--) {
if ((num[i] - '0') % 2 != 0) {
return num.Substring(0, i + 1);
}
}
return "";
}
public static void Main() {
Console.WriteLine(largestOddNumber("52"));
Console.WriteLine(largestOddNumber("4206"));
Console.WriteLine(largestOddNumber("35427"));
}
}This Python solution walks backwards through the string, looking for the first odd-numbered character, and returns the full string up to that character if found.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n) because of slicing operation.
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.
import re
def largestOddNumber(num: str) -> str:
match = re.search(r'[13579]', num[::-1])
return num[:len(num) - match.start()] if match else ""
print(largestOddNumber("52"))
print(largestOddNumber("4206"))
print(largestOddNumber("35427"))function largestOddNumber(num) {
const reversedNum = num.split('').reverse().join('');
const match = reversedNum.match(/[13579]/);
return match ? num.slice(0, num.length - match.index) : "";
}
console.log(largestOddNumber("52"));
console.log(largestOddNumber("4206"));
console.log(largestOddNumber("35427"));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.
Time Complexity: O(n), mainly due to the string reversal and regex search.
Space Complexity: O(n) for the reversed string.
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).
function largestOddNumber(num: string): string {
for (let i = num.length - 1; ~i; --i) {
if (Number(num[i]) & 1) {
return num.slice(0, i + 1);
}
}
return '';
}func largestOddNumber(num string) string {
for i := len(num) - 1; i >= 0; i-- {
c := num[i] - '0'
if (c & 1) == 1 {
return num[:i+1]
}
}
return ""
}Complexity comparison
| Approach | Complexity |
|---|---|
| Checking Last Odd Digit | Time Complexity: O(n), where n is the length of the string. |
| Using Regular Expression | Time Complexity: O(n), mainly due to the string reversal and regex search. |
| Reverse Traversal | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Checking Last Odd Digit (Greedy) | O(n) | O(1) | Best general solution. Single scan from the end with minimal memory. |
| Regular Expression Match | O(n) | O(n) | Useful in scripting languages when concise pattern matching is preferred. |
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.