You are given a string num representing a large integer. An integer is good if it meets the following conditions:
num with length 3.Return the maximum good integer as a string or an empty string "" if no such integer exists.
Note:
num or a good integer.
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 <= 1000num only consists of digits.Problem Overview: You are given a numeric string num. The task is to find the largest substring of length three where all digits are identical (like "777" or "000"). If multiple valid substrings exist, return the numerically largest one. If none exist, return an empty string.
Approach 1: Brute Force Check for Each Substring (O(n) time, O(1) space)
Scan the string and examine every substring of length three. For each index i, extract num[i], num[i+1], and num[i+2]. If all three characters match, you found a valid candidate like "444". Track the maximum digit seen so far and update the answer if the current digit is larger. Since each position is checked once and substring length is constant, the runtime stays O(n) with O(1) extra space. This approach is straightforward and works well when you want clear logic using simple iteration over a string.
Approach 2: Optimized Single Pass with Early Exit (O(n) time, O(1) space)
Instead of collecting candidates, track the best digit while scanning the string once. At each index, check if num[i] == num[i+1] == num[i+2]. When a valid triple appears, compare its digit with the current best. If you ever encounter "999", return immediately because no larger 3-digit repeated value exists. This early exit slightly improves practical performance. The algorithm still performs a linear scan with constant memory, making it optimal for large inputs. Conceptually this behaves like a fixed-size window similar to techniques used in sliding window problems, although the window size never changes.
The key observation: only substrings of length three matter, and the largest valid answer corresponds to the largest digit whose triple appears consecutively.
Recommended for interviews: Start with the substring check idea to demonstrate clarity. Then refine it into the single-pass optimized version that tracks the maximum digit and exits early when "999" appears. Interviewers typically expect the linear scan because it shows comfort with string traversal and constant-space optimization.
This approach involves iterating through the string, checking every possible substring of length 3 to see if it consists of the same character. If it does, keep track of the largest such substring found.
The C solution uses a for loop to traverse the string. For each substring of length 3, it checks if all characters are the same. If so, it compares it with the current maximum good integer stored in maxGood. It updates maxGood whenever a greater good integer is found. Finally, the largest such integer is returned.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), constant space is used.
This approach builds upon the basic iteration method, with an early termination feature if the maximum possible good integer ("999") is found. This can optimize cases where digits towards the start of the string quickly identify the upper bound, reducing unnecessary checks.
The optimized C solution works similarly to the brute force solution but includes a check to immediately return "999" once it's encountered because it represents the maximum possible good integer.
Time Complexity: Less than O(n) in the best case if "999" is early.
Space Complexity: O(1).
We can enumerate each digit i from large to small, where 0 \le i \le 9, and then check whether the string s consisting of three consecutive i is a substring of num. If it is, we directly return s.
If we have enumerated all the possible values of i and still haven't found a substring that satisfies the condition, we return an empty string.
The time complexity is O(10 times n), where n is the length of the string num. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force Check for Each Substring | Time Complexity: O(n), where n is the length of the string. |
| Optimized Single Pass with Early Exit | Time Complexity: Less than O(n) in the best case if "999" is early. |
| Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Check for Each Substring | O(n) | O(1) | Best for clarity and quick implementation when scanning fixed-length substrings. |
| Optimized Single Pass with Early Exit | O(n) | O(1) | Preferred in interviews and production for slightly better practical performance and early termination when "999" appears. |
Largest 3-Same-Digit Number in String | Leetcode 2264 • codestorywithMIK • 9,293 views views
Watch 9 more video solutions →Practice Largest 3-Same-Digit Number in String with our built-in code editor and test cases.
Practice on FleetCode