Largest 3-Same-Digit Number in String
EasyPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves two main stages. First, we iterate through the input string num to generate all possible length-3 substrings that are "good" integers (i.e., consist of three identical digits). These are stored in a list. In the second stage, we find the maximum string from this list. If the list is empty, it means no good integers were found.
Algorithm
- Create an empty list of strings,
goodIntegers, to store all found good integers. - Iterate through the input string
numfrom the first character up to the third-to-last character. - For each position
i, extract the substring of length 3 starting ati. - Check if all three characters of the substring are identical.
- If they are, add this substring to the
goodIntegerslist. - After iterating through the entire string, check if the
goodIntegerslist is empty. - If it is empty, return an empty string
"". - Otherwise, find the maximum string in the
goodIntegerslist (e.g., usingCollections.max()) and return it.
Walkthrough
This method systematically finds all valid 'good' integers and then picks the largest one from the collected candidates.
import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution { public String largestGoodInteger(String num) { List<String> goodIntegers = new ArrayList<>(); for (int i = 0; i <= num.length() - 3; i++) { if (num.charAt(i) == num.charAt(i + 1) && num.charAt(i + 1) == num.charAt(i + 2)) { goodIntegers.add(num.substring(i, i + 3)); } } if (goodIntegers.isEmpty()) { return ""; } // Collections.max finds the lexicographically largest string, which works for our case. return Collections.max(goodIntegers); }}Complexity
Time
O(N), where N is the length of `num`. The first loop to find candidates runs N-2 times. Finding the maximum in the list of candidates takes time proportional to the number of candidates, which is at most O(N).
Space
O(K), where K is the number of good integers found. In the worst-case scenario (e.g., a string like "999888777..."), the space complexity can be O(N), where N is the length of the input string.
Trade-offs
Pros
Conceptually straightforward, as it separates the problem into two distinct steps: finding all candidates and then selecting the best one.
Cons
Uses extra space proportional to the number of 'good' integers found, which can be up to O(N) in the worst case.
The two-pass nature (one to find all candidates, one to select the maximum) is less efficient than a single-pass solution.
This approach improves upon the generate-and-filter method by using a single pass through the string. Instead of storing all "good" integers, we maintain a single variable that keeps track of the maximum "good" integer found so far. As we iterate, if we find a new "good" integer, we compare it with our current maximum and update it if the new one is larger.
Algorithm
- Initialize a string variable,
maxGoodInteger, to an empty string"". This will store the result. - Iterate through the input string
numfrom indexi = 0tonum.length() - 3. - In each iteration, check if the characters at
i,i+1, andi+2are all identical. - If they are, it means we've found a "good" integer. Create the substring
currentGoodInteger = num.substring(i, i + 3). - Compare
currentGoodIntegerwithmaxGoodIntegerusing string comparison. - If
currentGoodIntegeris greater thanmaxGoodInteger, updatemaxGoodInteger = currentGoodInteger. - After the loop completes,
maxGoodIntegerwill hold the largest "good" integer found, or it will still be""if none were found. ReturnmaxGoodInteger.
Walkthrough
By keeping a running maximum, we eliminate the need for extra storage and a second pass. This is a classic optimization for 'find max/min' problems.
class Solution { public String largestGoodInteger(String num) { String maxGoodInteger = ""; for (int i = 0; i <= num.length() - 3; i++) { char c1 = num.charAt(i); char c2 = num.charAt(i + 1); char c3 = num.charAt(i + 2); if (c1 == c2 && c2 == c3) { String currentGoodInteger = num.substring(i, i + 3); // For strings of the same length representing numbers, // lexicographical comparison is equivalent to numerical comparison. if (currentGoodInteger.compareTo(maxGoodInteger) > 0) { maxGoodInteger = currentGoodInteger; } } } return maxGoodInteger; }}Complexity
Time
O(N), where N is the length of `num`. We iterate through the string once. Substring creation and comparison take constant time since the length is fixed at 3.
Space
O(1). We only use a few variables to store the result and loop index. The space for the temporary substring is constant (length 3).
Trade-offs
Pros
Efficient in both time and space.
Solves the problem in a single pass without needing extra data structures like a list.
Easy to understand and implement.
Cons
Involves creating new string objects and performing string comparisons inside the loop whenever a "good" integer is found, which has slightly more overhead than just comparing characters or integers.
This is the most optimized approach. It recognizes that to find the largest 3-same-digit number, we only need to find the largest single digit that appears three times consecutively. Instead of creating, storing, and comparing substrings like "777" and "333", we can just track the digits '7' and '3'. This avoids string manipulation inside the loop, making it faster in practice.
Algorithm
- Initialize an integer variable
maxDigitto a sentinel value like -1, which indicates that no "good" integer has been found yet. - Iterate through the string
numfromi = 0tonum.length() - 3. - Check if
num.charAt(i),num.charAt(i+1), andnum.charAt(i+2)are all the same. - If they are, get the numeric value of the current digit (e.g.,
num.charAt(i) - '0'). - Compare this numeric value with
maxDigitand updatemaxDigitif the current digit is larger (maxDigit = Math.max(maxDigit, currentValue)). - After the loop finishes, check the value of
maxDigit. - If
maxDigitis still -1, no "good" integer was found, so return"". - Otherwise, construct the result string by repeating the character representation of
maxDigitthree times and return it.
Walkthrough
This method minimizes operations within the main loop by avoiding string creation and comparison entirely. It relies on simple and fast character and integer comparisons, building the final result string only once after the loop concludes.
class Solution { public String largestGoodInteger(String num) { int maxDigit = -1; for (int i = 0; i <= num.length() - 3; i++) { if (num.charAt(i) == num.charAt(i + 1) && num.charAt(i + 1) == num.charAt(i + 2)) { // 'c' - '0' gives the integer value of a digit character 'c'. int currentDigit = num.charAt(i) - '0'; if (currentDigit > maxDigit) { maxDigit = currentDigit; } } } if (maxDigit == -1) { return ""; } // Build the result string from the max digit found. return String.valueOf(maxDigit) + String.valueOf(maxDigit) + String.valueOf(maxDigit); }}Complexity
Time
O(N), where N is the length of `num`. A single pass is performed with only character and integer comparisons inside the loop.
Space
O(1). We only use a single integer variable (`maxDigit`) to track the state during the loop. The final result string is of constant size.
Trade-offs
Pros
Most efficient approach in terms of constant factors due to minimal operations inside the loop.
Avoids all string creation and comparisons within the loop, relying only on fast character and integer operations.
Maintains O(N) time and O(1) space complexity.
Cons
The logic might be slightly less direct to read for a beginner compared to the string comparison approach, but it's a standard and valuable optimization technique.
Solutions
Solution
class Solution {public String largestGoodInteger(String num) { for (int i = 9; i >= 0; i--) { String s = String.valueOf(i).repeat(3); if (num.contains(s)) { return s; } } return ""; }}class Solution {public: string largestGoodInteger(string num) { for (char i = '9'; i >= '0'; --i) { string s(3, i); if (num.find(s) != string ::npos) { return s; } } return ""; }};class Solution: def largestGoodInteger(self, num: str) -> str: for i in range(9, - 1, - 1): if (s: = str(i) * 3) in num: return s return ""Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.