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.
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 ""; }}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.