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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: Less than O(n) in the best case if "999" is early.
Space Complexity: O(1).
| 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. |
Largest 3-Same-Digit Number in String - Leetcode 2264 - Python • NeetCodeIO • 5,731 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