Largest 3-Same-Digit Number in String

Problem Statement

In this task, you're presented with a string num that represents a large integer. You need to determine if there exists any "good" integer within this string. An integer qualifies as "good" if it meets both of the following criteria:

• The integer is a substring of the string num and has exactly three characters.
• All characters within this substring are the same, meaning it has only one unique digit.

Your goal is to identify the largest "good" integer and return it as a string. In cases where no such integer exists, you should return an empty string "". Please note that the substrings can include leading zeroes.

Examples

Example 1

Input:

num = "6777133339"

Output:

"777"

Explanation:

There are two distinct good integers: "777" and "333".  
"777" is the largest, so we return "777".

Example 2

Input:

num = "2300019"

Output:

"000"

Explanation:

"000" is the only good integer.

Example 3

Input:

num = "42352338"

Output:

""

Explanation:

No substring of length 3 consists of only one unique digit. Therefore, there are no good integers.

Constraints

• 3 <= num.length <= 1000
• num only consists of digits.

Approach and Intuition

From the examples and constraints provided, the solution requires checking every possible substring of length 3 within num to see if all characters are identical. Here’s a clear breakdown of the methodical approach:

1. Initialize an empty string max_good to store the result.

2. Loop through the string num from the start to length-2 (inclusive) to ensure each iteration gives us a valid substring of length 3:

   • For each index i, extract the substring from i to i+3.
   • Check if all characters in this substring are the same.
   • If they are the same and this substring is numerically greater than the current max_good, update max_good.

3. After the loop, return max_good if it's not empty. Otherwise, return an empty string "".

This approach leverages string slicing and comparisons to efficiently find the desired substring. Given the constraint (num.length up to 1000), this method is computationally reasonable as it operates in linear time relative to the size of the input string.

Solutions

class Solution {
public:
    string largestTriple(string digits) {
        // Initial value to compare with
        char highest = '\0';
    
        // Loop through the digits with a window of size 3
        for (int i = 0; i <= digits.length() - 3; ++i) {
            // Compare and check for three identical consecutive digits
            if (digits[i] == digits[i + 1] && digits[i] == digits[i + 2]) {
                // Update highest if necessary
                highest = max(highest, digits[i]);
            }
        }
    
        // Return result, based on whether we found any triple or not
        return highest == '\0' ? "" : string(3, highest);
    }
};