2264. Largest 3-Same-Digit Number in String

Ever faced a coding problem that seems complex at first but has a surprisingly simple and elegant solution? The “Largest 3-Same-Digit Number in String” problem is exactly that. Let’s break it down from the ground up.

The challenge is simple: given a string of digits like "6777133339", find the largest “good” integer. A “good” integer is a three-character substring made of only one unique digit (like "777" or "333"). In our example, the answer would be "777".

Intuition: The Detective Analogy 🕵️

The most intuitive way to solve this isn’t to scan the string from left to right. Instead, think like a detective with a “most wanted” list. You’re looking for a trio of identical digits, and your list is ordered from most valuable to least: "999", "888", "777", and so on.

You don’t search the crime scene randomly. You check for your #1 suspect ("999") first. If you find them, your job is done! You’ve found the biggest prize. If not, you move to your #2 suspect ("888"), then #3 ("777"), and so on.

This “top-down” approach is incredibly efficient because the first match you find is guaranteed to be the largest possible one.

Approach: Go for the Nines, then Decline

Based on our intuition, the approach is straightforward:

1. Start with the Best: Begin by looking for the best possible “good integer,” which is "999".

2. Loop and Check: Iterate downwards from 9 to 0. In each step, create the target string (e.g., for i=7, create "777").

3. Search the String: Check if this target string exists as a substring within the main input string.

4. First Hit Wins: The moment you find a match, return that string immediately. You don’t need to look any further.

5. Handle No Results: If you loop through all the numbers from 9 down to 0 and find no matches, it means no “good integer” exists. In this case, you return an empty string "".

Complexity Analysis

This approach is not only simple but also very performant.

• Time Complexity: O(N) The for loop runs a constant 10 times (from 9 down to 0). The main work is done by the includes() method, which, in the worst case, has to scan the entire input string of length N. This gives us a complexity of 10 * N, which simplifies to O(N). The runtime scales linearly with the size of the input string.

• Space Complexity: O(1) The algorithm uses a fixed amount of extra memory regardless of the input string’s size. We only store a loop counter and a 3-character string. This makes the space complexity constant, or O(1).

Complexity	Value	Explanation
Time	O(N)	The code may need to scan the input string.
Space	O(1)	It uses a fixed amount of extra memory.

Code in JavaScript

Here is the complete, clean JavaScript code implementing our strategy.

/**
 * @param {string} num The input string representing a large integer.
 * @return {string} The maximum "good integer" as a string, or "" if none exists.
 */
const largestGoodInteger = function(num) {
    // Loop from 9 down to 0. This ensures we check for the
    // largest possible good integers first.
    for (let i = 9; i >= 0; i--) {
        // Construct the three-digit string, e.g., "999", "888", etc.
        const goodInteger = String(i).repeat(3);

        // If the input string includes our target, we've found our answer.
        if (num.includes(goodInteger)) {
            // Since we're searching from the top down, the first match
            // is guaranteed to be the largest.
            return goodInteger;
        }
    }

    // If the loop finishes, no good integer was found.
    return "";
};

// Example:
console.log(largestGoodInteger("6777133339")); // Output: "777"
console.log(largestGoodInteger("2300019"));    // Output: "000"
console.log(largestGoodInteger("42352338"));   // Output: ""

How to Remember the Solution

To lock this strategy in your memory, just use this simple mnemonic:

“Go for the Nines, then Decline.”

This phrase instantly reminds you to:

1. Go for the Nines: Start by checking for "999".

2. Then Decline: If you don’t find it, just decline to the next number ("888", "777", etc.) until you get a hit.

It’s a simple, direct, and efficient way to crack this problem every time. Happy coding!