☕ DSA Java Articles

Topics › Strings › Basic and Easy String Problems

Largest Odd Number in a String

Easy TUF ID 394 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given a string num that represents a non-negative integer written in decimal digits. Among all non-empty substrings of num that represent an odd number, return the one with the largest value, as a string. If no substring is odd, return the empty string "".

Constraints: 1 ≤ |num| ≤ 10^5, num consists only of digits 0-9 and has no leading zeros. The number can have a hundred thousand digits, so it does not fit in any primitive type; the answer must be produced as a string.

Example 1

num = "52"
answer = "5"           // the odd substrings are "5" only; "52" and "2" are even

Example 2

num = "4206"
answer = ""            // every digit is even, so every substring is even

Example 3

num = "35427"
answer = "35427"       // the whole string ends in 7, which is odd, and nothing is larger

Approach 1: Brute force, try every substring

Intuition. An integer is odd exactly when its last digit is odd, so a substring num[i..j] is odd exactly when num[j] is 1, 3, 5, 7 or 9. The direct method enumerates all n(n+1)/2 substrings, keeps the ones that end in an odd digit, and remembers the largest. The one non-obvious part is comparing two candidates: they can have thousands of digits, so parsing them into long is not an option. Two digit strings without leading zeros compare by length first and then lexicographically, so we strip leading zeros (a substring such as "023" can have them even though num itself does not) and apply that rule.

Algorithm.

  1. For every start i and every end j ≥ i:
  2. If num[j] is odd, take cand = num.substring(i, j + 1).
  3. If best is empty or cand is numerically greater than best, set best = cand.
  4. Return best.
static String bruteForce(String num) {
    String best = "";
    int n = num.length();
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if ((num.charAt(j) - '0') % 2 == 1) {              // num[i..j] ends in an odd digit, so it is odd
                String cand = num.substring(i, j + 1);
                if (best.isEmpty() || isGreater(cand, best)) best = cand;
            }
        }
    }
    return best;
}

static boolean isGreater(String a, String b) {
    String x = stripLeadingZeros(a), y = stripLeadingZeros(b);
    if (x.length() != y.length()) return x.length() > y.length();
    return x.compareTo(y) > 0;
}

static String stripLeadingZeros(String s) {
    int k = 0;
    while (k < s.length() - 1 && s.charAt(k) == '0') k++;
    return s.substring(k);
}

Complexity. Time O(n^3): O(n^2) substrings, and each comparison (with its substring copy) costs O(n). Space O(n) for the current candidate and the best so far.

For n = 10^5 this is hopeless, but it is a useful baseline: it is obviously correct, and the tests in the Java file run both methods against the same expected answers.

Approach 2: Optimal, the prefix ending at the rightmost odd digit

Intuition. Two observations shrink the search space to a single candidate.

First, fix the position j of the last digit. Among all substrings that end at j, the longest one, num[0..j], is the largest: it has the most digits, and because num has no leading zeros its first digit is non-zero, so more digits really means a bigger number. So only prefixes matter.

Second, among the prefixes that end in an odd digit, the longest one is the largest, for the same reason. The longest such prefix ends at the rightmost odd digit. So the answer is num.substring(0, i + 1) where i is the last index holding an odd digit, or "" if there is none.

Scanning from the right also has a nice practical property: most random digit strings have an odd digit within the last couple of positions, so the loop usually stops almost immediately.

Algorithm.

  1. For i from n - 1 down to 0:
  2. If num[i] is odd, return num.substring(0, i + 1).
  3. If the loop finishes, return "".
static String optimal(String num) {
    for (int i = num.length() - 1; i >= 0; i--) {
        if ((num.charAt(i) - '0') % 2 == 1) return num.substring(0, i + 1);
    }
    return "";
}

Dry run on num = "123456":

i num[i] odd? action
5 6 no continue
4 5 yes return num.substring(0, 5) = "12345"

And on num = "4206": 6, 0, 2, 4 are all even, the loop runs out, and the answer is "".

Complexity. Time O(n) in the worst case (all digits even, or the only odd digit is the first one). Space O(1) extra; the returned substring is the answer itself and is required by the problem.

Why the brute force and the optimal answer agree

It is worth seeing why the two methods always produce the same string, not just the same numeric value. The optimal prefix P = num[0..i] is the unique longest odd substring: any odd substring ends at some odd index j ≤ i, so its length is at most i + 1, with equality only for P itself. A substring with fewer digits after stripping zeros is numerically smaller than P (which has no zeros to strip), and the brute force only replaces best when a candidate is strictly greater. Hence the brute force settles on P as well, never on an equal-valued variant such as "023" versus "23".

Edge cases and pitfalls