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 <= 105num only consists of digits and does not contain any leading zeros.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.
C++
Java
Python
C#
JavaScript
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.
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.
JavaScript
Time Complexity: O(n), mainly due to the string reversal and regex search.
Space Complexity: O(n) for the reversed string.
| 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. |
Largest Odd Number in String | Amazon | Leetcode 1903 • codestorywithMIK • 11,328 views views
Watch 9 more video solutions →Practice Largest Odd Number in String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor