Largest 3-Same-Digit Number in String — Problem & Solution
Largest 3-Same-Digit Number in String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Largest 3-Same-Digit Number in String is an easy coding problem on strings, asked in Amazon and Wipro interviews.
- Difficulty: Easy
- Topics: Strings
- Asked at: Amazon, Wipro
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A good substring is a length-3 substring of num whose three digits are all the same.
Given a digit string num, return the largest good substring as a string, or the empty string if there is none. The answer keeps its three characters, so "000" is a valid answer.
Example 1
Input: num = "6777133339"
Output: 777
Example 2
Input: num = "2300019"
Output: 000
Example 3
Input: num = "42352338"
Output:
Explanation: No digit repeats three times in a row.
Constraints
3 <= num.length <= 1000num consists of digits only.
Hints for Largest 3-Same-Digit Number in String
Hint 1
Slide a window of size 3 and test whether all three characters agree.
Hint 2
Comparing two length-3 digit strings lexicographically is the same as comparing them numerically.
Hint 3
Keep the largest match seen, starting from the empty string.
How to solve Largest 3-Same-Digit Number in String
Only n - 2 windows exist, and since all candidates have the same length, string comparison and numeric comparison agree — so no parsing is needed.
Approach
- Start with
best = "". - For each
ifrom 0 ton - 3, checknum[i] == num[i+1] == num[i+2]. - If they match, compare the substring with
bestand keep the larger. - Return
best.
Why it works
Equal-length digit strings order identically under lexicographic and numeric comparison, so the maximum found by string comparison is the numerically largest good integer. Keeping the string preserves the required leading zeros.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Parsing candidates to integers loses the leading zeros —
"000"would print as"0". - Scanning
iup ton - 1reads past the end of the string. - Since only 10 distinct answers exist, you could scan digits 9 down to 0 and search for the first triple — but the direct sweep is simpler.
Reference solution
Python
def largestGoodInteger(num: str) -> str:
best = ""
for i in range(len(num) - 2):
if num[i] == num[i + 1] == num[i + 2]:
cand = num[i:i + 3]
if cand > best:
best = cand
return bestJava
public static String largestGoodInteger(String num) {
String best = "";
for (int i = 0; i + 2 < num.length(); i++) {
if (num.charAt(i) == num.charAt(i + 1) && num.charAt(i) == num.charAt(i + 2)) {
String cand = num.substring(i, i + 3);
if (cand.compareTo(best) > 0) best = cand;
}
}
return best;
}C++
string largestGoodInteger(string num) {
string best = "";
for (int i = 0; i + 2 < (int) num.size(); i++) {
if (num[i] == num[i + 1] && num[i] == num[i + 2]) {
string cand = num.substr(i, 3);
if (cand > best) best = cand;
}
}
return best;
}JavaScript
var largestGoodInteger = function(num) {
let best = "";
for (let i = 0; i + 2 < num.length; i++) {
if (num.charAt(i) === num.charAt(i + 1) && num.charAt(i) === num.charAt(i + 2)) {
const cand = num.slice(i, i + 3);
if (cand > best) best = cand;
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings