# Largest Odd Number in String
**Difficulty:** EASY
[External](https://leetcode.com/problems/largest-odd-number-in-string)
Canonical: https://scaleengineer.com/dsa/problems/largest-odd-number-in-string
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
---
## 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 <= 105`
* `num` only consists of digits and does not contain any leading zeros.

# Approaches
## Brute-Force Substring Generation
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.
**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.
**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.
### Explanation
This method systematically generates all contiguous subsequences of the input string `num`. For each generated substring, we perform two main checks:

1.  **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.

2.  **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.

```java
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;
    }
}
```
### Algorithm
- Initialize a string variable `maxOdd` to an empty string `""`.
- Use a nested loop to generate all possible substrings of `num`. The outer loop `i` determines the start index, and the inner loop `j` determines 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`, update `maxOdd`.
- After iterating through all substrings, return `maxOdd`.

## Greedy Single Pass from Right
A highly efficient solution can be derived from a key insight: to get the largest possible number, we want the longest possible string. A number is odd if its last digit is odd. Therefore, the largest-valued odd substring must be the longest prefix of the original string that ends with an odd digit. This simplifies the problem to finding the rightmost odd digit.
**Time:** O(N), where N is the length of the string. In the worst-case scenario, we traverse the entire string once. The substring operation is called at most once. · **Space:** O(1) auxiliary space. The space for the returned substring can be up to O(N), but this is typically not counted as auxiliary space.
**Pros:** Extremely efficient with linear time complexity.; Simple and concise implementation.; Optimal solution for the given constraints.
**Cons:** The logic relies on a key insight that might not be immediately obvious.
### Explanation
The core idea is that any odd number must end in an odd digit. To maximize the value of the number, we should maximize its length. Let's say the rightmost odd digit in `num` is at index `k`.

The prefix `P = num.substring(0, k + 1)` is an odd number. Now, consider any other odd substring `S = num.substring(i, j + 1)`. For `S` to be odd, `num.charAt(j)` must be an odd digit. Since `k` is the index of the *rightmost* odd digit, it must be that `j <= k`.

- If `j < k`, then `S` is shorter than `P`, so `P` is a larger number.
- If `j = k`, then `S` is a suffix of `P` (i.e., `S = num.substring(i, k+1)` where `i >= 0`). Since the problem states no leading zeros, the full prefix `P` is always greater than or equal to any of its suffixes `S`.

Thus, the largest odd number is simply the prefix ending at the rightmost odd digit. Our algorithm is to find this digit by scanning from the right and then return the corresponding prefix.

```java
class Solution {
    public String largestOddNumber(String num) {
        for (int i = num.length() - 1; i >= 0; i--) {
            // Get the numeric value of the character
            int digit = num.charAt(i) - '0';
            
            // Check if the digit is odd
            if (digit % 2 != 0) {
                // Found the rightmost odd digit.
                // The largest odd number is the prefix ending at this digit.
                return num.substring(0, i + 1);
            }
        }
        
        // No odd digit was found in the entire string
        return "";
    }
}
```
### Algorithm
- Iterate through the input string `num` from right to left, starting from the last character at index `n-1`.
- In each iteration, get the character and check if its numeric value is odd.
- If an odd digit is found at index `i`, it means we have found the rightmost odd digit.
- The largest odd number must be the prefix of the string ending at this index. Return the substring from the beginning up to this index (inclusive), i.e., `num.substring(0, i + 1)`.
- If the loop completes without finding any odd digits, it implies that no odd number can be formed. In this case, return an empty string `""`.

# Solutions
### Java

```java
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 "";
  }
}

```

### JavaScript

```javascript
/** * @param {string} num * @return {string} */ var largestOddNumber =
  function (num) {
    for (let i = num.length - 1; ~i; --i) {
      if (Number(num[i]) & 1) {
        return num.slice(0, i + 1);
      }
    }
    return "";
  };

```

### CPP

```cpp
class Solution {
public:
  string largestOddNumber(string num) {
    for (int i = num.size() - 1; i >= 0; --i) {
      int c = num[i] - '0';
      if ((c & 1) == 1) {
        return num.substr(0, i + 1);
      }
    }
    return "";
  }
};

```

### Python

```python
class Solution : def largestOddNumber ( self , num : str ) -> str : for i in range ( len ( num ) - 1 , - 1 , - 1 ): if ( int ( num [ i ]) & 1 ) == 1 : return num [: i + 1 ] return ''
```