PPractick

The problem

A lottery system stores huge ticket numbers as digit strings, far too long for any integer type. A promotion wants, for each ticket, the largest odd number that appears as a contiguous substring of it (or an empty string if there's none). It sounds like it needs every substring, but a number is odd exactly when its last digit is odd, and a longer prefix is a larger number. So the answer is just the prefix ending at the rightmost odd digit, found in one backwards scan.

Example: "35427" → "35427"; "4206" → ""; "10133890" → "1013389".

Function signature

string largestOddNumber(const string& num);  // digits only; leading zeros of the answer are stripped

Test cases

Input num	Output	Explanation
"52"	"5"	The rightmost odd digit is 5
"4206"	""	Every digit is even
"35427"	"35427"	It already ends in an odd digit
"10133890"	"1013389"	The rightmost odd digit is the 9
"7"	"7"
"0214638"	"21463"	Prefix "021463", with the leading zero stripped

(Confirm: the input contains only digits; leading zeros in the answer are removed, which LeetCode's inputs never have anyway.)

How interviewers phrase it

• "Return the largest-valued odd integer that is a non-empty substring of num" (LeetCode 1903).
• Striver's variant adds leading zeros to the input and expects them stripped.

Clarifying questions to ask

1. Can the string have leading zeros? Should they be removed from the answer?
2. What should be returned when there's no odd digit?
3. How long can the string be? (Too long for any integer type, so work with characters.)

Follow-ups to expect

1. "Why only prefixes?"
2. "Why the rightmost odd digit?"
3. "How do you compare numbers stored as strings?"
4. "Complexity?"

Related questions

• Remove K Digits Medium
• Valid Paranthesis Checker Hard
• Minimum number of bracket reversals to make an expression balanced Hard
• Check if String is Palindrome or Not Easy
• Stock Buy and Sell Easy
• Longest Common Prefix Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in