Largest Odd Number in String

Problem Statement

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 

More Problems Solutions