Coding

Largest Odd Number in a String

Asked atHHashedIn

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

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. (If no odd number is found, then return empty string.)

Input : s = "5347" Output : "5347" Explanation : The odd numbers formed by given strings are --> 5, 3, 53, 347, 5347. So the largest among all the possible odd numbers for given string is 5347.

Input : s = "0214638" Output : "21463" Explanation : The different odd numbers that can be formed by the given string are --> 1, 3, 21, 63, 463, 1463, 21463. We cannot include 021463 as the number contains leading zero. So largest odd number in given string is 21463.

Input : s = "0032579"

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

cpp

class Solution{	
public:		
    string largeOddNum(string& s){
        //your code goes here
    }
};

java

class Solution {    
    public String largeOddNum(String s) {
        //your code goes here
    }
}

python

class Solution:  
    def largeOddNum(self, s: str) -> str:
        #your code goes here

javascript

class Solution {
    largeOddNum(s) {
        //your code goes here
    }
}

csharp

class Solution
{
    public string LargeOddNum(string s)
    {
        // your code goes here
    }
}

func largeOddNum(s string) string {
    //your code goes here
    n := len(s)
    for i := n - 1; i >= 0; i-- {
        digit := s[i] - '0'
        if digit%2 == 1 {
            res := s[:i+1]
            
            firstNonZero := 0
            for firstNonZero < len(res)-1 && res[firstNonZero] == '0' {
                firstNonZero++
            }
            return res[firstNonZero:]
        }
    }
    return ""
}

Stuck? Show a way to structure it+

01Find the rightmost odd digit.
02If none exists, return empty.
03Take the prefix ending at that digit.
04Remove leading zeroes from that prefix, returning empty if nothing remains.

Reference answer

To maximize the numeric value, retain as many leading digits as possible, but the final digit must be odd. Therefore scan from the right for the first odd digit and take the prefix through it. The source allows leading zeroes but the output does not, so trim leading zeroes from that prefix; if trimming removes everything, return empty. The scan and trim are O(n). Do not search all substrings: any shorter valid substring cannot exceed the valid prefix once leading-zero normalization is considered.

Then expect these follow-ups

How would you find the largest even substring?
Tests: condition variation
Why is a prefix optimal among valid candidates?
Tests: greedy proof

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question