LeetCode 2264 - Largest 3-Same-Digit Number in String
The problem requires identifying the largest "good" integer from a given string of digits. A "good" integer is defined as a substring of length 3 where all digits are identical.
Difficulty: 🟢 Easy
Topics: String
Solution
Problem Understanding
The problem requires identifying the largest "good" integer from a given string of digits. A "good" integer is defined as a substring of length 3 where all digits are identical. The input string num represents a large integer but is provided as a string, which allows us to handle leading zeros and lengths up to 1000 without numeric overflow. The output should be a string representing the largest good integer, or an empty string if no such substring exists.
Key aspects to understand include:
- Substring requirement: The good integer must be a contiguous sequence of three digits from
num. - Single digit repetition: All three characters must be the same.
- Return format: The result must be a string, not an integer.
- Constraints: The input length is between 3 and 1000, and all characters are digits ('0'-'9'), so performance matters but is manageable with a single-pass solution.
Important edge cases include a string with no repeated triples (e.g., "12345"), strings where the only good integer contains zeros (e.g., "2300019"), and strings with multiple good integers where the largest must be selected (e.g., "6777133339"). The algorithm must handle leading zeros correctly and compare substrings lexicographically since they are single-digit repetitions.
Approaches
The brute-force approach would examine every possible substring of length 3 and check if all three characters are identical. While correct, this approach is somewhat inefficient for large strings because it repeatedly checks overlapping substrings, although with the constraint of length ≤ 1000, it is feasible.
A key insight for optimization is that we only need to check consecutive triples once. Since each substring has length 3, we can iterate linearly through the string, comparing three consecutive characters at a time. If they are identical, we update a variable tracking the maximum good integer found so far. This approach ensures we only traverse the string once, making it efficient and simple.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n) | O(1) | Check all substrings of length 3 for identical digits, updating the maximum. Linear in practice since only n-2 substrings exist. |
| Optimal | O(n) | O(1) | Single pass through string checking triples and updating maximum, no extra storage required. |
Algorithm Walkthrough
- Initialize a variable
max_goodto an empty string to keep track of the largest good integer found. - Iterate over the string from index 0 to
len(num) - 3, examining each substring of length 3. - For each substring
num[i:i+3], check if all three characters are identical. - If the substring is a good integer and is larger than the current
max_good(lexicographically), updatemax_good. - After the iteration completes, return
max_good. If no good integer was found, it will remain an empty string.
Why it works: The invariant is that max_good always stores the largest good integer encountered so far. By checking each triple exactly once and updating only if it is larger than the current maximum, the algorithm guarantees that the final value of max_good is the largest possible good integer in the string.
Python Solution
class Solution:
def largestGoodInteger(self, num: str) -> str:
max_good = ""
for i in range(len(num) - 2):
if num[i] == num[i+1] == num[i+2]:
substring = num[i:i+3]
if substring > max_good:
max_good = substring
return max_good
This Python implementation follows the algorithm exactly. We iterate through num checking each triple for equality. When a triple is found, it is compared to max_good lexicographically, which works because all good integers have length 3. This ensures that the largest triple is selected. If no good triple is found, the function returns the initialized empty string.
Go Solution
func largestGoodInteger(num string) string {
maxGood := ""
for i := 0; i <= len(num)-3; i++ {
if num[i] == num[i+1] && num[i+1] == num[i+2] {
substring := num[i:i+3]
if substring > maxGood {
maxGood = substring
}
}
}
return maxGood
}
In Go, the logic mirrors Python. We iterate through the string and check if three consecutive bytes are equal. If so, we compare the substring to the current maximum using string comparison. Go strings support lexicographical comparison directly, so this is safe and efficient.
Worked Examples
Example 1: num = "6777133339"
| i | Substring | Good? | max_good |
|---|---|---|---|
| 0 | "677" | No | "" |
| 1 | "777" | Yes | "777" |
| 2 | "771" | No | "777" |
| 3 | "713" | No | "777" |
| 4 | "133" | No | "777" |
| 5 | "333" | Yes | "777" |
| 6 | "333" | Yes | "777" |
| 7 | "339" | No | "777" |
Return "777".
Example 2: num = "2300019"
| i | Substring | Good? | max_good |
|---|---|---|---|
| 0 | "230" | No | "" |
| 1 | "300" | No | "" |
| 2 | "000" | Yes | "000" |
| 3 | "001" | No | "000" |
| 4 | "019" | No | "000" |
Return "000".
Example 3: num = "42352338"
All substrings fail the good integer condition. Return "".
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | We iterate through the string once, checking triples. Each check is O(1). |
| Space | O(1) | Only a single string variable max_good is used, no additional data structures. |
The linear time complexity is justified since each of the n-2 triples is checked exactly once. No extra memory beyond the output string is needed.
Test Cases
# Provided examples
assert Solution().largestGoodInteger("6777133339") == "777" # multiple good integers
assert Solution().largestGoodInteger("2300019") == "000" # single good integer with zeros
assert Solution().largestGoodInteger("42352338") == "" # no good integers
# Boundary tests
assert Solution().largestGoodInteger("111") == "111" # minimum length with good integer
assert Solution().largestGoodInteger("123") == "" # minimum length, no good integer
assert Solution().largestGoodInteger("000111222333") == "333" # multiple candidates, pick largest
# Edge tests
assert Solution().largestGoodInteger("987654321000") == "000" # trailing zeros
assert Solution().largestGoodInteger("9999999") == "999" # all identical digits
assert Solution().largestGoodInteger("1010101010") == "" # alternating digits, no triple
| Test | Why |
|---|---|
| "6777133339" | Multiple good integers, must select the largest |
| "2300019" | Single good integer with leading zeros |
| "42352338" | No good integers present |
| "111" | Minimum input length with a good integer |
| "123" | Minimum input length with no good integer |
| "000111222333" | Multiple candidates, must correctly pick the largest |
| "987654321000" | Good integer at the end of the string |
| "9999999" | All digits identical, longest run handled correctly |
| "1010101010" | Alternating digits, no triple, ensures no false positives |
Edge Cases
One critical edge case is when the string contains leading zeros, like "00100". A naive numeric comparison would misinterpret these, but lexicographical string comparison correctly identifies "000" as a good integer.
Another edge case is when all digits are the same, such as "9999999". The implementation correctly identifies the first and subsequent triples, always keeping track of the maximum. Even overlapping triples are considered valid.
A third edge case is when there is no good integer at all, e.g., "123456". The algorithm correctly returns an empty string by maintaining an initially empty max_good and only updating it upon finding a valid triple. This ensures no false positives.