Largest Odd Number in String

problem links: leetcode, geekforgeeks.

Problem Statement

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.

Example 1:

Input: num = "52"
Output: "5"

Explanation: The only non-empty substrings are "5", "2", and "52". "5" is the only odd number.

Example 2:

Input: num = "4206"
Output: ""

Explanation: There are no odd numbers in "4206".

Example 3:

Input: num = "35427"
Output: "35427"

Explanation: "35427" is already an odd number.

Constraints:

1 <= num.length <= 105
num only consists of digits and does not contain any leading zeros.

Intuition

We are given a string and we need to find the longest odd number possible from it.

To check if the no is odd or not we only need to see the last digit of the no, if it's even the number is even and it is odd then the number is odd. We will use this concept to find the answer.

The idea is to integrate the string from n-1 to 0 and check if the character at i is odd or even, if it is odd then we got out the answer.

Approach

Find the length of the string.
We start a loop from n-1 to 0, i is the loop control variable, and this will traverse the string from right to left.
For each index of i we will check if the number is odd or not.
If we didn't find any odd number until i becomes less than 0, we return an empty string.

Example

num = "1234"
n = 4;

initialize i = n-1

when i = 3, num[i] = 4.
num[i]%2 == 1 | false

when i = 2, num[i] = 3.
num[i]%2 == 1 | true, so we return substring from (0,i+1) i.e "123"

Solution

C++

class Solution {
public:
    string largestOddNumber(string num) {

        int n = num.size();

        for(int i=n-1;i>=0;i--){

            if((num[i] - '0')%2 == 1)
                return num.substr(0,i+1);
        }

        return "";
    }
};

Java

class Solution {
    public String largestOddNumber(String num) {

        int n = num.length();
        for(int i=n-1;i>=0;i--){

            if((num.charAt(i) - '0')%2 == 1)
                return num.substring(0,i+1);
         }

        return "";
    }
}

Time Complexity

if n is the size of the string. Then the worst-case time complexity will be O(n).

Space Complexity

The space complexity of this solution is O(1) or constant space complexity.

Thank you for reading the post, I hope this would have helped you to understand the question better and the solution helped you to get a clear understanding of the approach used.

Feel free to drop any comments, I would have to solve your queries and improve my solution.

Largest Odd Number in String - Leetcode #1903