Largest Odd Number in String
On this page 
Problem Statement Solution 1: Naive Approach Solution 2: From Right to Left Solution 3: Check Last Digit Solution 4: Using Regular Expressions Solution 5: Binary Search Solution 6: Sliding Window Solution 7: Dynamic Programming Solution 8: Stack-Based Approach Solution 9: Greedy Approach Solution 10: String Manipulation More Problems Solutions
Problem Statement
You are given a string num that represents a large integer. Your task is to find and return the largest odd integer that can be obtained as a non-empty substring of num. If no odd integer exists within the string, return an empty string.
Example 1
Input: num = "52"
Output: "5"
Example 2
Input: num = "4206"
Output: ""
Example 3
Input: num = "35427"
Output: "35427"
Solution 1: Naive Approach
function largestOddSubstringNaive(num) {
let largestOdd = "";
for (let i = 0; i < num.length; i++) {
for (let j = i + 1; j <= num.length; j++) {
let substring = num.slice(i, j);
if (parseInt(substring) % 2 !== 0 && substring.length > largestOdd.length) {
largestOdd = substring;
}
}
}
return largestOdd;
}
const num1 = "52";
largestOddSubstringNaive(num1); //output: 5
const num2 = "4206";
largestOddSubstringNaive(num2); //output:
const num3 = "35427";
largestOddSubstringNaive(num3); //output: 35427
Solution 2: From Right to Left
function largestOddSubstringRightToLeft(num) {
for (let i = num.length - 1; i >= 0; i--) {
if (num[i] % 2 !== 0) {
return num.slice(0, i + 1);
}
}
return "";
}
const num1 = "52";
largestOddSubstringRightToLeft(num1); //output: 5
const num2 = "4206";
largestOddSubstringRightToLeft(num2); //output:
const num3 = "35427";
largestOddSubstringRightToLeft(num3); //output: 35427
Solution 3: Check Last Digit
function largestOddSubstringLastDigit(num) {
let largestOdd = "";
// Scan the string from the end
for (let i = num.length - 1; i >= 0; i--) {
if (num[i] % 2 !== 0) {
largestOdd = num.slice(0, i + 1);
break;
}
}
return largestOdd;
}
const num1 = "52";
largestOddSubstringLastDigit(num1); //output: 5
const num2 = "4206";
largestOddSubstringLastDigit(num2); //output:
const num3 = "35427";
largestOddSubstringLastDigit(num3); //output: 35427
Solution 4: Using Regular Expressions
function largestOddSubstringRegex(num) {
let match = num.match(/.*[13579]/g);
return match ? match[match.length - 1] : "";
}
const num1 = "52";
largestOddSubstringRegex(num1); //output: 5
const num2 = "4206";
largestOddSubstringRegex(num2); //output:
const num3 = "35427";
largestOddSubstringRegex(num3); //output: 35427
Solution 5: Binary Search
function largestOddSubstringEfficient(num) {
let largestOdd = "";
// Scan from right to left
for (let i = num.length - 1; i >= 0; i--) {
if (num[i] % 2 !== 0) {
largestOdd = num.slice(0, i + 1);
break;
}
}
return largestOdd;
}
const num1 = "52";
largestOddSubstringEfficient(num1); //output: 5
const num2 = "4206";
largestOddSubstringEfficient(num2); //output:
const num3 = "35427";
largestOddSubstringEfficient(num3); //output: 35427
Solution 6: Sliding Window
function largestOddSubstringSlidingWindow(num) {
let largestOdd = "";
let windowStart = 0;
for (let windowEnd = 0; windowEnd < num.length; windowEnd++) {
if (num[windowEnd] % 2 !== 0) {
largestOdd = num.slice(windowStart, windowEnd + 1);
}
}
return largestOdd;
}
const num1 = "52";
largestOddSubstringSlidingWindow(num1); //output: 5
const num2 = "4206";
largestOddSubstringSlidingWindow(num2); //output:
const num3 = "35427";
largestOddSubstringSlidingWindow(num3); //output: 35427
Solution 7: Dynamic Programming
function largestOddSubstringDP(num) {
let dp = Array(num.length).fill("");
let largestOdd = "";
for (let i = 0; i < num.length; i++) {
dp[i] = num[i] % 2 !== 0 ? num[i] : "";
if (dp[i].length > largestOdd.length) {
largestOdd = dp[i];
}
for (let j = i - 1; j >= 0; j--) {
dp[i] = num.slice(j, i + 1);
if (parseInt(dp[i]) % 2 !== 0 && dp[i].length > largestOdd.length) {
largestOdd = dp[i];
}
}
}
return largestOdd;
}
const num1 = "52";
largestOddSubstringDP(num1); //output: 5
const num2 = "4206";
largestOddSubstringDP(num2); //output:
const num3 = "35427";
largestOddSubstringDP(num3); //output: 35427
Solution 8: Stack-Based Approach
function largestOddSubstringStack(num) {
let stack = [];
let largestOdd = "";
for (let i = 0; i < num.length; i++) {
if (num[i] % 2 !== 0) {
stack.push(num.slice(0, i + 1));
}
}
while (stack.length > 0) {
let candidate = stack.pop();
if (candidate.length > largestOdd.length) {
largestOdd = candidate;
}
}
return largestOdd;
}
const num1 = "52";
largestOddSubstringStack(num1); //output: 5
const num2 = "4206";
largestOddSubstringStack(num2); //output:
const num3 = "35427";
largestOddSubstringStack(num3); //output: 35427
Solution 9: Greedy Approach
function largestOddSubstringGreedy(num) {
for (let i = num.length - 1; i >= 0; i--) {
if (num[i] % 2 !== 0) {
return num.slice(0, i + 1);
}
}
return "";
}
const num1 = "52";
largestOddSubstringGreedy(num1); //output: 5
const num2 = "4206";
largestOddSubstringGreedy(num2); //output:
const num3 = "35427";
largestOddSubstringGreedy(num3); //output: 35427
Solution 10: String Manipulation
function largestOddSubstringStringManipulation(num) {
let largestOdd = "";
for (let i = 0; i < num.length; i++) {
for (let j = i; j < num.length; j++) {
let substring = num.substring(i, j + 1);
if (parseInt(substring) % 2 !== 0 && substring.length > largestOdd.length) {
largestOdd = substring;
}
}
}
return largestOdd;
}
const num1 = "52";
largestOddSubstringStringManipulation(num1); //output: 5
const num2 = "4206";
largestOddSubstringStringManipulation(num2); //output:
const num3 = "35427";
largestOddSubstringStringManipulation(num3); //output: 35427