Problem Statement

Given a string s, representing a large integer, the task is to return the largest-valued odd integer (as a string) that is a substring of the given string s. The number returned should not have leading zero's. But the given input string may have leading zero.

A substring is a contiguous sequence of characters within a string. A null string (“”) is also a substring.

Examples

Example 1

Input : s = "504"
Output : "5"

Explanation : The some of the possible numbers formed from the string are 5, 50, 504, 0, 4.
There is only one odd number i.e. 5.

Example 2

Input : s = "2024"
Output : ""

Explanation : There is no odd digit is given string, so It is impossible to create a odd number.

Constraints

1 <= s.length <= 103
'0' <= s[i] <= '9'

Approaches

1️⃣ Iterating from backward

Intuition:

To determine the largest substring ending with an odd digit, start by iterating backward from the end of the number. This approach efficiently finds the rightmost odd digit by examining each character in reverse order. Once an odd digit is encountered, the substring from the beginning of the number up to and including this digit represents the largest possible odd-ending substring. This process leverages the fact that finding the last occurrence of an odd digit directly provides the longest valid substring.

Approach:

1. Start by iterating through the string from the end towards the beginning to find the first odd digit. This digit marks the potential end of the largest odd number substring.
2. Once an odd digit is found, skip any leading zeroes from the beginning of the string up to this odd digit.
3. Extract and return the substring starting after the leading zeroes and ending at the identified odd digit. This substring represents the largest odd integer without leading zeroes.

Dry Run:

index    0     1     2     3     4     5
      -------------------------------------
str   |  3  |  6  |  6  |  3  |  5  |  2  |
      -------------------------------------
                                       ^
                                       |
                                       i
  setting 'i' to the end of the str, continue decreasing i till
  we get the first odd digit.

First Pass

index    0     1     2     3     4     5
      -------------------------------------
str   |  3  |  6  |  6  |  3  |  5  |  2  |
      -------------------------------------
                                       ^
                                       |
                                       i
    str[i] is an even digit
    so, decrement i.

Second Pass

index    0     1     2     3     4     5
      -------------------------------------
str   |  3  |  6  |  6  |  3  |  5  |  2  |
      -------------------------------------
                                 ^
                                 |
                                 i
    str[i] is an odd digit
    so, stop the iterations.

index    0     1     2     3     4     5
      -------------------------------------
str   |  3  |  6  |  6  |  3  |  5  |  2  |
      -------------------------------------
         ^                        ^
         |                        |
       start                      i (end)
 
 Return the substring from 0(start) to end(i).

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to find the largest odd number 
    that is a substring of given string */
    string largeOddNum(string& s) {
        int ind = -1;
        
        // Iterate through the string from the end to beginning
        int i;
        for (i = s.length() - 1; i >= 0; i--) {
            // Break if an odd digit is found
            if ((s[i] - '0') % 2 == 1) {
                ind = i;
                break;
            }
        }
        
        // Skipping any leading zeroes
        i = 0;
        while(i <= ind && s[i] == '0') i++;
        
        // Return the largest odd number substring
        return s.substr(i, ind - i + 1);
    }
};

int main() {
    Solution solution;
    string num = "504";
    string result = solution.largeOddNum(num);
    cout << "Largest odd number: " << result << endl;
    return 0;
}

Complexity Analysis:

• Time Complexity O(N): The loop runs once through the string of length N.
• Space Complexity O(1): No extra data structures are used only a few extra variables are used which does not affect the complexity as much.