Problem Description

You are given a string num that represents a large integer. Your task is to find the maximum "good" integer within this string.

A "good" integer must satisfy two conditions:

1. It must be a substring of num with exactly length 3
2. It must consist of only one unique digit (all three digits are the same)

For example, "777", "000", or "333" would be good integers since they have length 3 and all digits are identical. However, "123" or "001" would not be good integers because they contain different digits.

The goal is to return the maximum good integer as a string. If no such good integer exists in num, return an empty string "".

Key points to note:

• A substring is a contiguous sequence of characters, meaning the three digits must appear consecutively in the original string
• Leading zeroes are allowed, so "000" is a valid good integer
• You need to find the maximum among all possible good integers (e.g., if both "222" and "777" exist in num, you should return "777")

The solution approach iterates from the largest possible good integer "999" down to "000", checking if each exists as a substring in num. The first match found is returned since we're checking from largest to smallest, ensuring we get the maximum good integer.

Intuition

Since we're looking for the maximum "good" integer, and a good integer must consist of three identical digits, there are only 10 possible good integers: "000", "111", "222", ..., "999".

The key insight is that among these 10 possibilities, "999" is the largest, followed by "888", "777", and so on, down to "000". Rather than scanning through the entire string num to find all good integers and then comparing them, we can be smarter about our search.

We can start by checking if "999" exists as a substring in num. If it does, we immediately know it's the maximum good integer since no other good integer can be larger. If "999" doesn't exist, we check "888", then "777", and continue downward.

This greedy approach works because:

1. The total number of possible good integers is small (only 10)
2. We can easily generate each good integer by repeating a single digit three times: str(i) * 3
3. By checking from largest to smallest, the first match we find is guaranteed to be the maximum

The beauty of this solution is its simplicity - instead of finding all good integers and then determining the maximum, we directly search for the maximum by checking possibilities in descending order. This turns what could be a more complex string parsing problem into a straightforward enumeration of 10 cases.

Solution Approach

The implementation follows a straightforward enumeration strategy:

1. Iterate from 9 down to 0: We use a for loop with range(9, -1, -1) to iterate through digits from 9 to 0 in descending order. This ensures we check for larger good integers first.

2. Generate each possible good integer: For each digit i, we create the corresponding good integer by repeating the digit three times: str(i) * 3. This gives us strings like "999", "888", "777", etc.

3. Check substring existence: We use Python's in operator to check if the generated three-digit string exists as a substring in num. The expression s in num returns True if s is found anywhere within num.

4. Return immediately upon finding: As soon as we find a good integer that exists in num, we return it. Since we're checking from largest to smallest, this guarantees we return the maximum good integer.

5. Handle no match case: If the loop completes without finding any good integer (none of "999" through "000" exist in num), we return an empty string "".

The code uses a compact Python feature - the walrus operator := - which allows us to assign the generated string to variable s while simultaneously using it in the condition check. This makes the code more concise:

if (s := str(i) * 3) in num:
    return s

The time complexity is O(n) where n is the length of num, since in the worst case we might check all 10 possible good integers, and each substring check takes O(n) time. The space complexity is O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through the solution with the string num = "6777133339".

We want to find the maximum "good" integer (three identical consecutive digits) in this string.

Step 1: Check for "999"

• Generate: str(9) * 3 = "999"
• Check: Is "999" in "6777133339"? No
• Continue to next digit

Step 2: Check for "888"

• Generate: str(8) * 3 = "888"
• Check: Is "888" in "6777133339"? No
• Continue to next digit

Step 3: Check for "777"

• Generate: str(7) * 3 = "777"
• Check: Is "777" in "6777133339"?
• Looking at the string: "6777133339" - Yes! "777" exists at position 1-3
• Since we found a match, immediately return "777"

We don't need to check further (for "666", "555", etc.) because we're searching from largest to smallest. The first match we find is guaranteed to be the maximum good integer.

Note that "333" also exists in the string at positions 5-7, but since we found "777" first (which is larger), we correctly return "777" as the maximum good integer.

Another Example: If num = "222244400", the algorithm would:

• Check "999" → Not found
• Check "888" → Not found
• Check "777" → Not found
• Check "666" → Not found
• Check "555" → Not found
• Check "444" → Found at positions 4-6! Return "444"

Even though "222" and "000" also exist, we return "444" since it's the largest good integer present.

Solution Implementation

Time and Space Complexity

Time Complexity: O(10 × n) or simplified to O(n), where n is the length of the string num.

The algorithm iterates through 10 possible digits (from 9 down to 0). For each digit i, it creates a string pattern str(i) * 3 (which takes O(1) time) and checks if this pattern exists in the input string using the in operator. The substring search operation s in num takes O(n) time in the worst case, where n is the length of num. Since we perform this search at most 10 times (a constant), the overall time complexity is O(10 × n) = O(n).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space. The variable s stores a string of length 3 (like "999", "888", etc.), which requires O(1) space. The loop variable i also takes constant space. No additional data structures that scale with the input size are used, resulting in constant space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting to Parse and Compare as Integers

A common mistake is trying to convert substrings to integers for comparison, which fails when dealing with "000":

Incorrect approach:

def largestGoodInteger(self, num: str) -> str:
    max_good = -1
    for i in range(len(num) - 2):
        substring = num[i:i+3]
        if substring[0] == substring[1] == substring[2]:
            max_good = max(max_good, int(substring))  # Problem: int("000") = 0
    return str(max_good) if max_good != -1 else ""

This fails because int("000") equals 0, losing the original format. When comparing, "000" would incorrectly be considered smaller than other single-digit good integers.

Correct approach: Compare strings directly or iterate from largest to smallest as shown in the solution.

2. Incorrect String Comparison Logic

Another pitfall is assuming string comparison works the same as numeric comparison without considering lexicographic ordering:

Incorrect approach:

def largestGoodInteger(self, num: str) -> str:
    max_good = ""
    for i in range(len(num) - 2):
        substring = num[i:i+3]
        if substring[0] == substring[1] == substring[2]:
            max_good = max(max_good, substring)  # Works but less efficient
    return max_good

While this actually works correctly (since "999" > "888" > ... > "000" in lexicographic order), it's less efficient as it requires scanning the entire string and performing multiple comparisons.

3. Off-by-One Errors in Sliding Window

When manually implementing a sliding window approach, it's easy to make boundary errors:

Incorrect approach:

def largestGoodInteger(self, num: str) -> str:
    for i in range(len(num)):  # Should be len(num) - 2
        if i + 2 < len(num):  # Extra boundary check needed
            substring = num[i:i+3]
            # ... rest of logic

Better approach: Use range(len(num) - 2) to avoid index out of bounds errors naturally.

4. Not Handling Edge Cases

Forgetting to handle cases where the string length is less than 3:

Solution: The provided approach naturally handles this since the in operator will simply return False for strings shorter than the pattern being searched.