# Largest 3-Same-Digit Number in String
**Difficulty:** EASY
[External](https://leetcode.com/problems/largest-3-same-digit-number-in-string)
Canonical: https://scaleengineer.com/dsa/problems/largest-3-same-digit-number-in-string
**Data structures:** String
**Companies:** [opentext](https://scaleengineer.com/companies/opentext), [PayPay](https://scaleengineer.com/companies/paypay)
---
## 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 = "6**777**133339"
**Output:** "777"
**Explanation:** There are two distinct good integers: "777" and "333".
"777" is the largest, so we return "777".

**Example 2:**

**Input:** num = "23**000**19"
**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.

# Approaches
## Generate and Filter
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.
**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.
**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.
### Explanation
This method systematically finds all valid 'good' integers and then picks the largest one from the collected candidates.

```java
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);
    }
}
```
### Algorithm
*   Create an empty list of strings, `goodIntegers`, to store all found good integers.
*   Iterate through the input string `num` from the first character up to the third-to-last character.
*   For each position `i`, extract the substring of length 3 starting at `i`.
*   Check if all three characters of the substring are identical.
*   If they are, add this substring to the `goodIntegers` list.
*   After iterating through the entire string, check if the `goodIntegers` list is empty.
*   If it is empty, return an empty string `""`.
*   Otherwise, find the maximum string in the `goodIntegers` list (e.g., using `Collections.max()`) and return it.

## Single Pass with String Comparison
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.
**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).
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
*   Initialize a string variable, `maxGoodInteger`, to an empty string `""`. This will store the result.
*   Iterate through the input string `num` from index `i = 0` to `num.length() - 3`.
*   In each iteration, check if the characters at `i`, `i+1`, and `i+2` are all identical.
*   If they are, it means we've found a "good" integer. Create the substring `currentGoodInteger = num.substring(i, i + 3)`.
*   Compare `currentGoodInteger` with `maxGoodInteger` using string comparison.
*   If `currentGoodInteger` is greater than `maxGoodInteger`, update `maxGoodInteger = currentGoodInteger`.
*   After the loop completes, `maxGoodInteger` will hold the largest "good" integer found, or it will still be `""` if none were found. Return `maxGoodInteger`.

## Single Pass with Max Digit Tracking
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.
**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.
**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.
### Explanation
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.

```java
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);
    }
}
```
### Algorithm
*   Initialize an integer variable `maxDigit` to a sentinel value like -1, which indicates that no "good" integer has been found yet.
*   Iterate through the string `num` from `i = 0` to `num.length() - 3`.
*   Check if `num.charAt(i)`, `num.charAt(i+1)`, and `num.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 `maxDigit` and update `maxDigit` if the current digit is larger (`maxDigit = Math.max(maxDigit, currentValue)`).
*   After the loop finishes, check the value of `maxDigit`.
*   If `maxDigit` is still -1, no "good" integer was found, so return `""`.
*   Otherwise, construct the result string by repeating the character representation of `maxDigit` three times and return it.

# Solutions
### Java

```java
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 "";
  }
}

```

### CPP

```cpp
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 "";
  }
};

```

### Python

```python
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 ""

```