Largest Odd Number in String - Practice Coding Problems

Largest Odd Number in 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.

Input & Output

Example 1 — Basic Case with Odd Ending

$ Input: num = "52301"

› Output: "52301"

💡 Note: The entire string ends with '1' which is odd, so "52301" is the largest odd substring.

Example 2 — Even Ending, Find Rightmost Odd

$ Input: num = "5234"

› Output: "523"

💡 Note: The string ends with '4' (even), but '3' at position 2 is the rightmost odd digit, so we take "523".

Example 3 — No Odd Digits

$ Input: num = "246"

› Output: ""

💡 Note: All digits are even (2, 4, 6), so no odd substring exists. Return empty string.

Constraints

1 ≤ num.length ≤ 10⁵
num consists of only digits

Visualization

Tap to expand

Understanding the Visualization

Input String

Given string representing a large number

Find Strategy

Locate rightmost odd digit for maximum length

Extract Result

Take substring from start to that odd digit

Key Takeaway

🎯 Key Insight: The largest odd substring always ends with the rightmost odd digit

Asked in

G Google 25 a Amazon 20 M Microsoft 15

The key insight is that the largest odd substring always ends with the rightmost odd digit. Best approach is the greedy method: scan from right to left to find the first odd digit, then return substring from start to that position. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Substrings	O(n³)	O(n)	Generate all possible substrings and find the largest odd one
Greedy - Find Rightmost Odd Digit	O(n)	O(1)	Find the rightmost odd digit and return substring from start to that position

Brute Force - Check All Substrings — Algorithm Steps

Generate all possible substrings
Check if each substring represents an odd number
Keep track of the largest odd substring

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Substrings

Create all possible substrings

Check Odd

Test if each substring ends with odd digit

Find Largest

Keep track of largest odd substring

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(char* num) {
    int n = strlen(num);
    char* largestOdd = (char*)malloc((n + 1) * sizeof(char));
    largestOdd[0] = '\0';
    
    // Generate all possible substrings
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            char substring[n + 1];
            strncpy(substring, num + i, j - i);
            substring[j - i] = '\0';
            
            // Check if substring represents an odd number
            if (strlen(substring) > 0 && (substring[strlen(substring) - 1] - '0') % 2 == 1) {
                // Compare with current largest odd substring
                if (strlen(largestOdd) == 0 || strlen(substring) > strlen(largestOdd) || 
                    (strlen(substring) == strlen(largestOdd) && strcmp(substring, largestOdd) > 0)) {
                    strcpy(largestOdd, substring);
                }
            }
        }
    }
    
    return largestOdd;
}

int main() {
    char num[100001];
    fgets(num, sizeof(num), stdin);
    num[strcspn(num, "\n")] = 0;
    
    char* result = solution(num);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

O(n²) substrings × O(n) string comparison for each

⚠ Quadratic Growth

Space Complexity

O(n)

Storage for substring generation and comparison

⚡ Linearithmic Space

25.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Substrings — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler