easy Largest Odd Number in String

Problem Statement

Given a large integer num represented as string, return the largest-valued odd integer (represented as a string) that is a non-empty substring of num. If no such number exists, the result should be an empty string.

A substring is defined as a contiguous sequence of characters within a string.

Examples

Example 1:
- Input: num = "238946"
- Expected Output: "2389"
- Justification: The largest odd number in the string is "2389".
Example 2:
- Input: num = "2804"
- Expected Output: ""
- Justification: Since there are no odd numbers in the input string, the output is an empty string.
Example 3:
- Input: num = "13579"
- Expected Output: "13579"
- Justification: The entire input string is the largest odd number itself, as all digits are odd.

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — Largest Odd Number in String — problem

1. Why / judgment

Largest-value odd integer substring that is a prefix of num as numeric value means: find the rightmost odd digit and take num[0..thatIndex]. Any longer odd substring not aligned as that prefix would start later and be numerically smaller for same digit length, and shorter prefixes ending earlier are smaller. Pattern: scan from right for odd digit — not generate all substrings.

2. Big-O derivation (K11)

O(n) right-to-left scan O(1) extra (output slice O(n)).
Brute all substrings O(n²) refuse.

3. Pattern + when-NOT (K12)

Name: RIGHTMOST ODD DIGIT PREFIX

Recognition: largest odd number as substring of digit string.

When-NOT: Largest odd subsequence non-contiguous → different. Need smallest odd → other criteria. Leading zeros policies — input usually no weird leading zeros except 0.

4. Edge hand-run (K13)

all even → "".
ends odd → whole string.
"238946" → "2389".
"4206" → "".
"13579" → all.

5. Interviewer follow-ups (model answers)

Q1. Why prefix to rightmost odd?
A: Among odd-ending substrings, the one with leftmost start 0 and furthest odd end maximizes value.

Q2. Single odd digit in middle?
A: Prefix through that digit — includes left digits, correct for max value.

Q3. Empty result?
A: No odd digits.

6. Short drills

Drill: "52" → "5".
Drill: "44" → "".
Drill: prove no internal substring beats that prefix.

✅ Solution Largest Odd Number in String

Problem Statement

A substring is defined as a contiguous sequence of characters within a string.

Examples

Example 1:
- Input: num = "238946"
- Expected Output: "2389"
- Justification: The largest odd number in the string is "2389".
Example 2:
- Input: num = "2804"
- Expected Output: ""
- Justification: Since there are no odd numbers in the input string, the output is an empty string.
Example 3:
- Input: num = "13579"
- Expected Output: "13579"
- Justification: The entire input string is the largest odd number itself, as all digits are odd.

Solution

To solve this problem, we'll iterate through the string from right to left, searching for the first odd digit. Odd digits make a number odd, so finding any such digit means the substring up to and including that digit is the largest odd number we can form.

This approach works because trimming any digits to the right of the found odd digit will not affect the oddness of the number, and since we're scanning from right to left, we ensure the largest possible odd number is found. This method is efficient because it requires only a single pass through the string, making it optimal for both time and space complexity.

Step-by-step Algorithm

Start by checking if the input string is empty. If yes, return an empty string immediately.
Iterate through the string from the last character to the first:
- For each character, check if it is an odd digit (1, 3, 5, 7, or 9).
  - If an odd digit is found, return the substring from the start of the string to this digit's index (inclusive).
If no odd digit is found by the end of the iteration, return an empty string, indicating no odd number can be formed.

Algorithm Walkthrough

Given input: "238946"

Start from the last digit ("6") and move leftward.
6 is even, move to 4.
4 is even, move to 9.
9 is odd, so we take the substring from the start to this digit, which gives "2389".
Return "2389" as the largest odd number that can be formed.

Code

java

public class Solution {

  // Method to find the largest odd number in string
  public String largestOddNumber(String num) {
    // Iterate from the end of the string towards the beginning
    for (int i = num.length() - 1; i >= 0; i--) {
      // Check if the current digit is odd
      if ((num.charAt(i) - '0') % 2 != 0) {
        // Return the substring from start to the current odd digit
        return num.substring(0, i + 1);
      }
    }
    // Return an empty string if no odd digit is found
    return "";
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Test the method with example inputs
    System.out.println(solution.largestOddNumber("238946")); // "2389"
    System.out.println(solution.largestOddNumber("5804")); // "5"
    System.out.println(solution.largestOddNumber("13579")); // "13579"
  }
}

Complexity Analysis

Time Complexity

The time complexity for the algorithm in all provided languages is , where n is the length of the input string. This is because, in the worst case, the algorithm scans through the entire string once to find the first odd digit from the right.

Space Complexity

The space complexity is . The algorithm uses a fixed amount of space to store intermediate variables, regardless of the input size.

🎯 STRICT STANDOUT — Solution Largest Odd Number in String

1. Why / judgment

A number is odd iff its last digit is odd. Among all odd-ending prefixes of the digit string, the longest (rightmost odd digit as the end) is numerically largest. Algorithm: scan from the right; first odd digit at i returns num[0..i]; none returns empty. Judgment: refuse generating all O(n^2) substrings.

2. Big-O derivation (K11)

n = len(num). One right-to-left scan: O(n) char checks.
Return slice is O(n) copy worst-case.
No nested loops: Theta(n) time, O(1) extra if return view / O(n) for new string.
238946: right scan 6e,4e,9 odd -> 2389. 2804: all even -> empty.
Derivation: at most n checks; each O(1) parity.

3. Pattern + when-NOT (K12)

Name: RIGHTMOST ODD DIGIT / PREFIX CUT

Recognition: largest odd integer that is a contiguous substring of a digit string.

When-NOT: Need largest odd among non-contiguous selections -> subsequence problem. Need all odd substrings counted -> enumeration/DP. Numeric type fits in 64-bit -> still prefer string to avoid BigInt limits.

4. Edge hand-run (K13)

empty -> empty
single 7 -> 7; single 4 -> empty
52 -> 5; 2468 -> empty
all-odd 13579 -> whole string
leading zeros 0023 -> 0023

5. Interviewer follow-ups (model answers)

Q1. Why rightmost odd, not leftmost?
A: Longer prefix ending at a later odd digit is a larger integer than a shorter earlier one sharing the left digits.

Q2. Is substring vs subsequence material?
A: Yes — problem forces contiguous; dropping middle digits invents numbers not present as substrings.

Q3. Complexity if you brute all substrings?
A: O(n^2) candidates — rejected under company n up to 1e5 string norms.

6. Short drills

Drill: 4206 -> empty
Drill: 23946 -> 239
Drill: prove two odd-ending prefixes, the longer is >= as number.

🧩 Pattern · Arrays

Recognize it: Scan once tracking what you need (running max/sum), or precompute a prefix-sum / hash → turn O(n²) into O(n).

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Largest Odd Number in String? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Largest Odd Number in String** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Largest Odd Number in String** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Largest Odd Number in String**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Largest Odd Number in String**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Min Cost Climbing Stairs Binary Tree Paths →