2264. Largest 3-Same-Digit Number in String Solution

Q: Is Largest 3-Same-Digit Number in String easy or hard?

Largest 3-Same-Digit Number in String is classified as an Easy problem on LeetCode with an acceptance rate around 70%+. The challenge focuses on careful string iteration and recognizing valid substrings of fixed length rather than complex algorithms.

Q: Largest 3-Same-Digit Number in String Python/Java solution

The implementation is identical across languages: iterate from index 0 to n-3, check whether three consecutive characters are equal, and update the maximum digit found. Python, Java, C++, and JavaScript solutions all run in O(n) time and O(1) space since they only scan the string once.

Q: How to solve Largest 3-Same-Digit Number in String in O(n)?

Iterate through the string and check if three consecutive characters are equal: num[i] == num[i+1] == num[i+2]. When a match appears, compare its digit with the current maximum and update the answer. Continue scanning until the end or exit early if the substring "999" is found. The algorithm performs one pass and uses constant memory.

Q: What is the best approach for Largest 3-Same-Digit Number in String?

The best approach is a single linear scan that checks every 3-character window and tracks the largest repeated digit found. Each step compares num[i], num[i+1], and num[i+2]. If all match, update the maximum digit candidate. This runs in O(n) time with O(1) extra space and can exit early if "999" appears.

Q: Is Largest 3-Same-Digit Number in String asked at Google/Amazon/Meta?

This problem represents a typical easy-level string scanning question often used in screening rounds or practice sets. Similar substring pattern detection problems appear in interviews at large tech companies like Amazon, Google, and Meta to evaluate basic string manipulation and iteration skills.

Q: What data structure is used in Largest 3-Same-Digit Number in String?

The problem mainly uses a string traversal technique. No additional data structures are required because the algorithm simply compares characters in a fixed-size window and tracks the best digit using a variable. Space usage remains constant.

Q: What is the time complexity of Largest 3-Same-Digit Number in String?

The time complexity is O(n), where n is the length of the string. Each index is inspected once while checking a constant-size substring of length three. The space complexity is O(1) because only a few variables are used to track the best result.

The problem

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 num with length 3.
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 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 <= 1000
num only consists of digits.

Approach overview

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 1: Brute Force Check for Each Substring

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.

Python

def largestGoodInteger(num: str) -> str:
    max_good = ""
    for i in range(len(num) - 2):
        if num[i] == num[i+1] == num[i+2]:
            curr = num[i:i+3]
            if curr > max_good:
                max_good = curr
    return max_good

num = "6777133339"
print(largestGoodInteger(num))

Java

public class Solution {
    public String largestGoodInteger(String num) {
        String maxGood = "";
        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)) {
                String curr = num.substring(i, i+3);
                if (curr.compareTo(maxGood) > 0) {
                    maxGood = curr;
                }
            }
        }
        return maxGood;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.largestGoodInteger("6777133339"));
    }
}

C++

#include <iostream>
#include <string>
using namespace std;

string largestGoodInteger(string num) {
    string maxGood = "";
    for (int i = 0; i <= num.size() - 3; ++i) {
        if (num[i] == num[i + 1] && num[i + 1] == num[i + 2]) {
            string curr = num.substr(i, 3);
            if (curr > maxGood) {
                maxGood = curr;
            }
        }
    }
    return maxGood;
}

int main() {
    string num = "6777133339";
    cout << largestGoodInteger(num) << endl;
    return 0;
}

JavaScript

function largestGoodInteger(num) {
    let maxGood = "";
    for (let i = 0; i <= num.length - 3; i++) {
        if (num[i] === num[i+1] && num[i+1] === num[i+2]) {
            let curr = num.substring(i, i + 3);
            if (curr > maxGood) {
                maxGood = curr;
            }
        }
    }
    return maxGood;
}

console.log(largestGoodInteger("6777133339"));

#include <stdio.h>
#include <string.h>

char* largestGoodInteger(char* num) {
    char maxGood[4] = "";
    int n = strlen(num);
    for (int i = 0; i <= n - 3; i++) {
        if (num[i] == num[i + 1] && num[i + 1] == num[i + 2]) {
            if (strncmp(&num[i], maxGood, 3) > 0) {
                strncpy(maxGood, &num[i], 3);
                maxGood[3] = '\0';
            }
        }
    }
    return strdup(maxGood);
}

int main() {
    char num[] = "6777133339";
    printf("%s\n", largestGoodInteger(num));
    return 0;
}

using System;

public class Solution {
    public string LargestGoodInteger(string num) {
        string maxGood = "";
        for (int i = 0; i <= num.Length - 3; i++) {
            if (num[i] == num[i+1] && num[i+1] == num[i+2]) {
                string curr = num.Substring(i, 3);
                if (curr.CompareTo(maxGood) > 0) {
                    maxGood = curr;
                }
            }
        }
        return maxGood;
    }
    public static void Main(string[] args) {
        Solution sol = new Solution();
        Console.WriteLine(sol.LargestGoodInteger("6777133339"));
    }
}

The Python solution uses string slicing and comparison to find and update the largest good integer within the loop. It checks each substring of length three for identical characters, compares and finds the maximum.

Complexity

Time Complexity: O(n).
Space Complexity: O(1).

Try this approach in the editor

Approach 2: Optimized Single Pass with Early Exit

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.

Python

def largestGoodIntegerOptimized(num: str) -> str:
    max_good = ""
    for i in range(len(num) - 2):
        if num[i] == num[i+1] == num[i+2]:
            if num[i] == '9': return "999"
            curr = num[i:i+3]
            if curr > max_good:
                max_good = curr
    return max_good

num = "779939999"
print(largestGoodIntegerOptimized(num))

Java

public class Solution {
    public String largestGoodIntegerOptimized(String num) {
        String maxGood = "";
        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)) {
                if (num.charAt(i) == '9') return "999";
                String curr = num.substring(i, i+3);
                if (curr.compareTo(maxGood) > 0) {
                    maxGood = curr;
                }
            }
        }
        return maxGood;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.largestGoodIntegerOptimized("779939999"));
    }
}

C++

#include <iostream>
#include <string>
using namespace std;

string largestGoodIntegerOptimized(string num) {
    string maxGood = "";
    for (int i = 0; i <= num.size() - 3; ++i) {
        if (num[i] == num[i + 1] && num[i + 1] == num[i + 2]) {
            if (num[i] == '9') return "999";
            string curr = num.substr(i, 3);
            if (curr > maxGood) {
                maxGood = curr;
            }
        }
    }
    return maxGood;
}

int main() {
    string num = "7779133339";
    cout << largestGoodIntegerOptimized(num) << endl;
    return 0;
}

JavaScript

function largestGoodIntegerOptimized(num) {
    let maxGood = "";
    for (let i = 0; i <= num.length - 3; i++) {
        if (num[i] === num[i+1] && num[i+1] === num[i+2]) {
            if (num[i] === '9') return "999";
            let curr = num.substring(i, i + 3);
            if (curr > maxGood) {
                maxGood = curr;
            }
        }
    }
    return maxGood;
}

console.log(largestGoodIntegerOptimized("779939999"));

#include <stdio.h>
#include <string.h>

char* largestGoodIntegerOptimized(char* num) {
    char maxGood[4] = "";
    int n = strlen(num);
    for (int i = 0; i <= n - 3; i++) {
        if (num[i] == num[i + 1] && num[i + 1] == num[i + 2]) {
            if (num[i] == '9') return "999";
            if (strncmp(&num[i], maxGood, 3) > 0) {
                strncpy(maxGood, &num[i], 3);
                maxGood[3] = '\0';
            }
        }
    }
    return strdup(maxGood);
}

int main() {
    char num[] = "6779133339";
    printf("%s\n", largestGoodIntegerOptimized(num));
    return 0;
}

using System;

public class Solution {
    public string LargestGoodIntegerOptimized(string num) {
        string maxGood = "";
        for (int i = 0; i <= num.Length - 3; i++) {
            if (num[i] == num[i+1] && num[i+1] == num[i+2]) {
                if (num[i] == '9') return "999";
                string curr = num.Substring(i, 3);
                if (curr.CompareTo(maxGood) > 0) {
                    maxGood = curr;
                }
            }
        }
        return maxGood;
    }
    public static void Main(string[] args) {
        Solution sol = new Solution();
        Console.WriteLine(sol.LargestGoodIntegerOptimized("798939999"));
    }
}

This Python version improves on the brute force by attempting to finish early if '999' is encountered, saving processing in cases where inputs allow it.

Complexity

Time Complexity: As low as O(1) conditionally, otherwise O(n).
Space Complexity: O(1).

Try this approach in the editor

Approach 3: Enumeration

We can enumerate each digit i from large to small, where 0 \le i \le 9, and then check whether the string s consisting of three consecutive i is a substring of num. If it is, we directly return s.

If we have enumerated all the possible values of i and still haven't found a substring that satisfies the condition, we return an empty string.

The time complexity is O(10 times n), where n is the length of the string num. The space complexity is O(1).

TypeScript

function largestGoodInteger(num: string): string {
    for (let i = 9; i >= 0; i--) {
        const s = String(i).repeat(3);
        if (num.includes(s)) {
            return s;
        }
    }
    return '';
}

func largestGoodInteger(num string) string {
	for c := '9'; c >= '0'; c-- {
		if s := strings.Repeat(string(c), 3); strings.Contains(num, s) {
			return s
		}
	}
	return ""
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Brute Force Check for Each Substring	Time Complexity: O(n). Space Complexity: O(1).
Optimized Single Pass with Early Exit	Time Complexity: As low as O(1) conditionally, otherwise O(n). Space Complexity: O(1).
Enumeration	–

Complexity analysis

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.

Frequently asked questions

Is Largest 3-Same-Digit Number in String easy or hard?

Largest 3-Same-Digit Number in String is classified as an Easy problem on LeetCode with an acceptance rate around 70%+. The challenge focuses on careful string iteration and recognizing valid substrings of fixed length rather than complex algorithms.

Largest 3-Same-Digit Number in String Python/Java solution

The implementation is identical across languages: iterate from index 0 to n-3, check whether three consecutive characters are equal, and update the maximum digit found. Python, Java, C++, and JavaScript solutions all run in O(n) time and O(1) space since they only scan the string once.

How to solve Largest 3-Same-Digit Number in String in O(n)?

Iterate through the string and check if three consecutive characters are equal: num[i] == num[i+1] == num[i+2]. When a match appears, compare its digit with the current maximum and update the answer. Continue scanning until the end or exit early if the substring "999" is found. The algorithm performs one pass and uses constant memory.

What is the best approach for Largest 3-Same-Digit Number in String?

The best approach is a single linear scan that checks every 3-character window and tracks the largest repeated digit found. Each step compares num[i], num[i+1], and num[i+2]. If all match, update the maximum digit candidate. This runs in O(n) time with O(1) extra space and can exit early if "999" appears.

Is Largest 3-Same-Digit Number in String asked at Google/Amazon/Meta?

This problem represents a typical easy-level string scanning question often used in screening rounds or practice sets. Similar substring pattern detection problems appear in interviews at large tech companies like Amazon, Google, and Meta to evaluate basic string manipulation and iteration skills.

What data structure is used in Largest 3-Same-Digit Number in String?

The problem mainly uses a string traversal technique. No additional data structures are required because the algorithm simply compares characters in a fixed-size window and tracks the best digit using a variable. Space usage remains constant.

What is the time complexity of Largest 3-Same-Digit Number in String?

The time complexity is O(n), where n is the length of the string. Each index is inspected once while checking a constant-size substring of length three. The space complexity is O(1) because only a few variables are used to track the best result.

Largest 3-Same-Digit Number in String solution and explanation

The problem

Approach overview

Approach 1: Brute Force Check for Each Substring

Approach 2: Optimized Single Pass with Early Exit

Approach 3: Enumeration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Largest 3-Same-Digit Number in String solution and explanation

The problem

Approach overview

Approach 1: Brute Force Check for Each Substring

Approach 2: Optimized Single Pass with Early Exit

Approach 3: Enumeration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems