Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Largest Odd Number in String

EASYProblemSolveExternal Links

Description

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. For example, the substrings of "523" are "5", "52", "523", "2", "23", and "3".

Examples

Example 1

Input: num = "52"

Output: "5"

Explanation: The non-empty substrings are "5", "2", and "52". Among these, the only odd number is "5" (since 5 ends in an odd digit). "52" ends in '2' which is even, and "2" itself is even. So we return "5".

Example 2

Input: num = "4206"

Output: ""

Explanation: The digits of "4206" are 4, 2, 0, and 6 — all even. No substring can form an odd number because every substring ends with an even digit. Return an empty string.

Example 3

Input: num = "35427"

Output: "35427"

Explanation: The entire string "35427" ends with '7', which is odd, so the whole string is already an odd number. Since it includes all digits, it is the largest possible odd substring. No longer substring exists, so we return "35427".

Constraints

  • 1 ≤ num.length ≤ 10^5
  • num only consists of digits and does not contain any leading zeros.

Editorial

Brute Force

Intuition

The most straightforward approach is to generate every possible substring of num, check which ones represent odd numbers, and then pick the largest.

A number is odd if and only if its last digit is odd (1, 3, 5, 7, or 9). So for each substring, we only need to look at its last character to determine if it's odd.

Among all odd substrings, the "largest" one is the one with the greatest numeric value. Since there are no leading zeros and all substrings start from some index in the original number string, a longer substring that starts earlier will always be larger than a shorter one. For example, "352" > "52" > "5" > "3" > "2".

So we can enumerate all substrings, filter for odd ones, and return the maximum. But this approach generates O(n²) substrings and comparing them can be costly.

Step-by-Step Explanation

Let's trace through with num = "52".

We generate all substrings and check which are odd:

Step 1: Enumerate substrings starting at index 0:

  • "5" (ends in '5', odd digit) → ODD ✓
  • "52" (ends in '2', even digit) → EVEN ✗

Step 2: Enumerate substrings starting at index 1:

  • "2" (ends in '2', even digit) → EVEN ✗

Step 3: Collect all odd substrings: ["5"].

Step 4: The largest (and only) odd substring is "5".

Result: "5".

For a longer example like num = "35427":

  • Odd substrings include: "3", "35", "354", "3542", "35427", "5", "54", "542", "5427", "4", "42", "427", "2", "27", "7", and many more. Among these, the odd ones are those ending in 3, 5, or 7.
  • The largest is "35427" since it contains all digits and is itself odd.

This works but generates O(n²) substrings, which is slow for n up to 10^5.

Algorithm

  1. Initialize result as an empty string.
  2. For each starting index i from 0 to n-1:
    • For each ending index j from i to n-1:
      • Extract substring num[i..j].
      • If the last character of this substring is an odd digit (1, 3, 5, 7, 9):
        • If this substring is longer than result, or same length but lexicographically larger, update result.
  3. Return result.

Code

#include <string>
using namespace std;

class Solution {
public:
    string largestOddNumber(string num) {
        string result = "";
        int n = num.size();
        
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                // Check if substring ends with an odd digit
                if ((num[j] - '0') % 2 == 1) {
                    string sub = num.substr(i, j - i + 1);
                    // Longer substring is always larger; same length compare lexicographically
                    if (sub.size() > result.size() || 
                        (sub.size() == result.size() && sub > result)) {
                        result = sub;
                    }
                }
            }
        }
        
        return result;
    }
};
class Solution:
    def largestOddNumber(self, num: str) -> str:
        result = ""
        n = len(num)
        
        for i in range(n):
            for j in range(i, n):
                # Check if substring ends with an odd digit
                if int(num[j]) % 2 == 1:
                    sub = num[i:j + 1]
                    # Longer substring is larger; same length compare normally
                    if len(sub) > len(result) or \
                       (len(sub) == len(result) and sub > result):
                        result = sub
                
        return result
class Solution {
    public String largestOddNumber(String num) {
        String result = "";
        int n = num.length();
        
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                // Check if substring ends with an odd digit
                if ((num.charAt(j) - '0') % 2 == 1) {
                    String sub = num.substring(i, j + 1);
                    // Longer substring is always larger
                    if (sub.length() > result.length() || 
                        (sub.length() == result.length() && sub.compareTo(result) > 0)) {
                        result = sub;
                    }
                }
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n²) or O(n³)

We generate O(n²) substrings. Each substring extraction and comparison can take O(n) time in the worst case, giving O(n³) total. Even with optimizations, we still examine O(n²) substrings.

With n up to 10^5, this is 10^10 operations in the worst case — far too slow.

Space Complexity: O(n)

We store the current best substring, which can be up to length n.

Why This Approach Is Not Efficient

The brute force checks all O(n²) substrings. With n up to 10^5, this produces up to 5 × 10^9 substrings — completely unacceptable for time limits.

But there's a much deeper insight we're missing. Let's think about what makes one odd substring larger than another.

Since the input string has no leading zeros, any substring that starts at index 0 and includes more digits will be larger than one that includes fewer digits. For instance, "3542" > "542" > "42" > "2". So among all odd substrings, the largest one will always start at index 0 (the beginning of the string).

If the largest odd substring always starts at index 0, then we don't need to try different starting positions at all! We just need to find the rightmost position where an odd digit occurs. The substring from the beginning up to and including that odd digit is our answer.

This transforms the problem from "enumerate all substrings" to "find the rightmost odd digit" — a single right-to-left scan in O(n) time.

Optimal Approach - Right-to-Left Scan

Intuition

The key insight comes from two observations:

Observation 1: A number is odd if and only if its last digit is odd.
This is a fundamental property — 123 is odd because 3 is odd, 456 is even because 6 is even.

Observation 2: Among substrings starting at index 0, the longer one is always larger.
Since there are no leading zeros, "354" is always larger than "35" is always larger than "3". More digits starting from the same position means a larger number.

Combining these two observations, the strategy becomes clear:

  • The largest odd substring must start at index 0 (to maximize length).
  • It must end at the rightmost odd digit (to include as many digits as possible while still being odd).

So we simply scan from right to left, find the first (rightmost) odd digit, and return the substring from the beginning up to that position.

Imagine reading a license plate number and being asked: "What's the largest odd number you can read from the left?" You'd scan from the right end, skip over any trailing even digits, and read from the start up to the first odd digit you find.

Step-by-Step Explanation

Let's trace through with num = "52348".

Step 1: Start scanning from the rightmost character.

  • Index 4: digit = '8'. Is 8 odd? No (8 % 2 = 0). Move left.

Step 2: Index 3: digit = '4'. Is 4 odd? No. Move left.

Step 3: Index 2: digit = '3'. Is 3 odd? YES! (3 % 2 = 1).

Step 4: Found the rightmost odd digit at index 2. Return substring from index 0 to index 2 inclusive.

  • Result: "523".

Let's also trace the edge case num = "4206".

Step 1: Index 3: digit = '6'. Even. Move left.
Step 2: Index 2: digit = '0'. Even. Move left.
Step 3: Index 1: digit = '2'. Even. Move left.
Step 4: Index 0: digit = '4'. Even. Move left.
Step 5: No more characters. No odd digit found.

  • Result: "" (empty string).

Right-to-Left Scan — Find the Rightmost Odd Digit — Watch as we scan from right to left, skipping even digits, until we find the first odd digit. Everything from the start up to that digit is our answer.

Now let's trace the edge case where no odd digit exists: num = "4206".

Right-to-Left Scan — No Odd Digit Found — Watch the scan traverse the entire string without finding any odd digit, resulting in an empty string answer.

Algorithm

  1. Start from the last character of num and move left (i = n-1 down to 0).
  2. At each position i, check if num[i] is an odd digit (1, 3, 5, 7, or 9).
  3. If it is odd, return the substring num[0..i] (from the beginning up to and including index i).
  4. If the loop finishes without finding any odd digit, return an empty string "".

Code

#include <string>
using namespace std;

class Solution {
public:
    string largestOddNumber(string num) {
        for (int i = num.size() - 1; i >= 0; i--) {
            if ((num[i] - '0') % 2 == 1) {
                return num.substr(0, i + 1);
            }
        }
        return "";
    }
};
class Solution:
    def largestOddNumber(self, num: str) -> str:
        for i in range(len(num) - 1, -1, -1):
            if int(num[i]) % 2 == 1:
                return num[:i + 1]
        return ""
class Solution {
    public String largestOddNumber(String num) {
        for (int i = num.length() - 1; i >= 0; i--) {
            if ((num.charAt(i) - '0') % 2 == 1) {
                return num.substring(0, i + 1);
            }
        }
        return "";
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the string at most once from right to left. Each character is examined at most once with a constant-time odd/even check. In the best case (last digit is odd), we return immediately in O(1). In the worst case (no odd digits, or the only odd digit is the first character), we scan all n characters.

Space Complexity: O(1)

We use only a single loop variable i. The returned substring is part of the output and does not count as auxiliary space. No additional data structures are needed.