Watch 10 video solutions for Largest 3-Same-Digit Number in String, a easy level problem involving String. This walkthrough by codestorywithMIK has 9,293 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |