Largest 3-Same-Digit Number in String - Solution & Explanation
Problem Statement
You are given a string num representing a large integer. An integer is good if it meets the following conditions:
- It is a substring of
numwith length3. - It consists of only one unique digit.
Return the maximum good integer as a string or an empty string "" if no such integer exists.
Note:
- A substring is a contiguous sequence of characters within a string.
- There may be leading zeroes in
numor 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 <= 1000numonly consists of digits.
Approach Overview
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.
Approach 1: Brute Force Check for Each Substring
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.
Complexity
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), constant space is used.
Approach 2: Optimized Single Pass with Early Exit
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.
Complexity
Time Complexity: Less than O(n) in the best case if "999" is early.
Space Complexity: O(1).
Approach 3: Enumeration
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).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Largest 3-Same-Digit Number in String | Leetcode 2264 • codestorywithMIK • 10,268 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Largest 3-Same-Digit Number in String easy or hard?
Largest 3-Same-Digit Number in String Python/Java solution
How to solve Largest 3-Same-Digit Number in String in O(n)?
What is the best approach for Largest 3-Same-Digit Number in String?
Is Largest 3-Same-Digit Number in String asked at Google/Amazon/Meta?
What data structure is used in Largest 3-Same-Digit Number in String?
What is the time complexity of Largest 3-Same-Digit Number in String?
Ready to solve this problem?
Practice Largest 3-Same-Digit Number in String with our built-in code editor and test cases.
Practice on FleetCode