Largest Odd Number in String
EasyPrompt
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.
Approaches
2 approaches with complexity analysis and trade-offs.
The most straightforward approach is to exhaustively check every possible substring of the input string num. For each substring, we determine if it represents an odd number. We then keep track of the largest odd number found throughout this process.
Algorithm
- Initialize a string variable
maxOddto an empty string"". - Use a nested loop to generate all possible substrings of
num. The outer loopidetermines the start index, and the inner loopjdetermines the end index. - For each substring, check if it represents an odd number by examining its last character (
num.charAt(j)). - If the substring is odd, compare it with
maxOdd. A number is larger if its string representation is longer. If lengths are equal, perform a lexicographical comparison. - If the current odd substring is larger than
maxOdd, updatemaxOdd. - After iterating through all substrings, return
maxOdd.
Walkthrough
This method systematically generates all contiguous subsequences of the input string num. For each generated substring, we perform two main checks:
-
Odd Number Check: A number is odd if and only if its last digit is odd. We can quickly check this by looking at the last character of the substring. If it's '1', '3', '5', '7', or '9', the number is odd.
-
Magnitude Comparison: If the substring is odd, we must compare it with the largest odd substring found so far. Since the numbers can be too large for standard integer types like
long, this comparison must be done on their string representations. A longer number string always represents a larger value. If two number strings have the same length, the one that is lexicographically greater is the larger number.
We start with an empty string as our maximum and update it whenever we find a larger odd substring.
class Solution { public String largestOddNumber(String num) { String maxOdd = ""; int n = num.length(); for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { char lastChar = num.charAt(j); // Check if the number ending at index j is odd if ((lastChar - '0') % 2 != 0) { String currentSub = num.substring(i, j + 1); // Compare with the largest odd number found so far if (isLarger(currentSub, maxOdd)) { maxOdd = currentSub; } } } } return maxOdd; } // Helper function to compare two number strings private boolean isLarger(String s1, String s2) { if (s2.isEmpty()) { return true; } if (s1.length() > s2.length()) { return true; } if (s1.length() < s2.length()) { return false; } return s1.compareTo(s2) > 0; }}Complexity
Time
O(N^3). There are O(N^2) possible substrings. For each substring, creation (`substring` method) and comparison can take up to O(N) time, leading to a cubic complexity.
Space
O(N), where N is the length of the input string. This space is used to store the current substring and the largest odd substring found.
Trade-offs
Pros
Simple to conceptualize and implement.
Directly translates the problem statement into code.
Cons
Extremely inefficient with a cubic time complexity, making it impractical for the given constraints.
Will likely result in a 'Time Limit Exceeded' error on most platforms.
Solutions
Solution
class Solution {public String largestOddNumber(String num) { for (int i = num.length() - 1; i >= 0; --i) { int c = num.charAt(i) - '0'; if ((c & 1) == 1) { return num.substring(0, i + 1); } } return ""; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.