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 _themaximum 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.

Examples

Example 1

1
2
3
4

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

1
2
3

Input: num = "23** _000_** 19"
Output: "000"
Explanation: "000" is the only good integer.

Example 3

1
2
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.

Solution

Method 1 – Sliding Window and Comparison

Intuition

To find the largest 3-same-digit substring, scan the string and check every group of three consecutive identical digits, keeping track of the largest found.

Approach

  1. Initialize an empty string for the answer.
  2. Iterate through the string, for each index i, check if num[i] == num[i+1] == num[i+2].
  3. If so, update the answer if this 3-digit substring is larger than the current answer.
  4. Return the answer (or "" if none found).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    string largestGoodInteger(string num) {
        string ans = "";
        for (int i = 0; i + 2 < num.size(); ++i) {
            if (num[i] == num[i+1] && num[i+1] == num[i+2]) {
                string s = num.substr(i, 3);
                if (s > ans) ans = s;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func largestGoodInteger(num string) string {
    ans := ""
    for i := 0; i+2 < len(num); i++ {
        if num[i] == num[i+1] && num[i+1] == num[i+2] {
            s := num[i:i+3]
            if s > ans { ans = s }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public String largestGoodInteger(String num) {
        String ans = "";
        for (int i = 0; i + 2 < num.length(); ++i) {
            if (num.charAt(i) == num.charAt(i+1) && num.charAt(i+1) == num.charAt(i+2)) {
                String s = num.substring(i, i+3);
                if (s.compareTo(ans) > 0) ans = s;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun largestGoodInteger(num: String): String {
        var ans = ""
        for (i in 0..num.length-3) {
            if (num[i] == num[i+1] && num[i+1] == num[i+2]) {
                val s = num.substring(i, i+3)
                if (s > ans) ans = s
            }
        }
        return ans
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def largestGoodInteger(self, num: str) -> str:
        ans = ""
        for i in range(len(num)-2):
            if num[i] == num[i+1] == num[i+2]:
                s = num[i:i+3]
                if s > ans:
                    ans = s
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn largest_good_integer(num: String) -> String {
        let bytes = num.as_bytes();
        let mut ans = "".to_string();
        for i in 0..bytes.len().saturating_sub(2) {
            if bytes[i] == bytes[i+1] && bytes[i+1] == bytes[i+2] {
                let s = &num[i..i+3];
                if s > ans { ans = s.to_string(); }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    largestGoodInteger(num: string): string {
        let ans = ""
        for (let i = 0; i + 2 < num.length; ++i) {
            if (num[i] === num[i+1] && num[i+1] === num[i+2]) {
                const s = num.slice(i, i+3)
                if (s > ans) ans = s
            }
        }
        return ans
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of num. Each character is checked once.
  • 🧺 Space complexity: O(1), only a few variables are used.