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

Description

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.

Topics

String

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

String Traversal - Iterating through characters in a string and accessing elements by index
Sliding Window (Fixed Size) - Examining consecutive elements of a fixed length (in this case, 3 characters)
String Comparison - Comparing strings lexicographically or converting substrings to integers for comparison

1. Brute Force

Intuition

We need to find the largest "good integer" in the string, where a good integer is a substring of length 3 consisting of the same digit repeated three times (like "111", "222", etc.). The straightforward approach is to scan through the string, check every window of size 3, and whenever we find three consecutive identical digits, we compare its numeric value to our current best and keep the larger one.

Algorithm

Initialize res as an empty string and val as 0 to track the largest good integer found.
Iterate through the string from index 0 to len(num) - 2:
- Check if the current character equals the next two characters.
- If so, extract the 3-character substring and convert it to an integer.
- If this value is greater than or equal to val, update both val and res.
Return res.

class Solution:
    def largestGoodInteger(self, num: str) -> str:
        res = ""
        val = 0

        for i in range(len(num) - 2):
            if num[i] == num[i + 1] == num[i + 2]:
                tmp = num[i : i + 3]
                if val <= int(tmp):
                    val = int(tmp)
                    res = tmp

        return res

public class Solution {
    public String largestGoodInteger(String num) {
        String res = "";
        int val = 0;

        for (int i = 0; i < num.length() - 2; i++) {
            if (num.charAt(i) == num.charAt(i + 1) &&
                num.charAt(i) == num.charAt(i + 2)) {
                String tmp = num.substring(i, i + 3);
                if (val <= Integer.parseInt(tmp)) {
                    val = Integer.parseInt(tmp);
                    res = tmp;
                }
            }
        }

        return res;
    }
}

class Solution {
public:
    string largestGoodInteger(string num) {
        string res = "";
        int val = 0;

        for (int i = 0; i < num.length() - 2; i++) {
            if (num[i] == num[i + 1] && num[i] == num[i + 2]) {
                string tmp = num.substr(i, 3);
                if (val <= stoi(tmp)) {
                    val = stoi(tmp);
                    res = tmp;
                }
            }
        }

        return res;
    }
};

class Solution {
    /**
     * @param {string} num
     * @return {string}
     */
    largestGoodInteger(num) {
        let res = '';
        let val = 0;

        for (let i = 0; i < num.length - 2; i++) {
            if (num[i] === num[i + 1] && num[i] === num[i + 2]) {
                const tmp = num.slice(i, i + 3);
                if (val <= parseInt(tmp)) {
                    val = parseInt(tmp);
                    res = tmp;
                }
            }
        }

        return res;
    }
}

public class Solution {
    public string LargestGoodInteger(string num) {
        string res = "";
        int val = 0;

        for (int i = 0; i < num.Length - 2; i++) {
            if (num[i] == num[i + 1] && num[i] == num[i + 2]) {
                string tmp = num.Substring(i, 3);
                int tmpVal = int.Parse(tmp);
                if (val <= tmpVal) {
                    val = tmpVal;
                    res = tmp;
                }
            }
        }

        return res;
    }
}

class Solution {
    fun largestGoodInteger(num: String): String {
        var res = ""
        var value = 0

        for (i in 0 until num.length - 2) {
            if (num[i] == num[i + 1] && num[i] == num[i + 2]) {
                val tmp = num.substring(i, i + 3)
                val tmpVal = tmp.toInt()
                if (value <= tmpVal) {
                    value = tmpVal
                    res = tmp
                }
            }
        }

        return res
    }
}

class Solution {
    func largestGoodInteger(_ num: String) -> String {
        var res = ""
        var val = 0
        let chars = Array(num)

        for i in 0..<(chars.count - 2) {
            if chars[i] == chars[i + 1] && chars[i] == chars[i + 2] {
                let tmp = String(chars[i..<(i + 3)])
                let tmpVal = Int(tmp)!
                if val <= tmpVal {
                    val = tmpVal
                    res = tmp
                }
            }
        }

        return res
    }
}

impl Solution {
    pub fn largest_good_integer(num: String) -> String {
        let bytes = num.as_bytes();
        let mut res = String::new();
        let mut val = 0;

        for i in 0..bytes.len() - 2 {
            if bytes[i] == bytes[i + 1] && bytes[i] == bytes[i + 2] {
                let tmp = &num[i..i + 3];
                let tmp_val: i32 = tmp.parse().unwrap();
                if val <= tmp_val {
                    val = tmp_val;
                    res = tmp.to_string();
                }
            }
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

2. Iteration

Intuition

Instead of tracking both the numeric value and the string separately, we can simplify by using string comparison. Since all good integers have the same length (3 characters), lexicographic comparison works correctly for finding the maximum. For example, "999" > "888" > "777" when compared as strings. We just need to handle the edge case where "000" is a valid result but we need to distinguish it from "no good integer found."

Algorithm

Initialize res to "0" as a baseline for comparison.
Iterate through the string, checking each window of size 3:
- If three consecutive characters are the same, compare the substring with res and keep the larger one.
If res is still "0" and "000" was never found, return an empty string. Otherwise, return res.

class Solution:
    def largestGoodInteger(self, num: str) -> str:
        res = "0"

        for i in range(len(num) - 2):
            if num[i] == num[i + 1] == num[i + 2]:
                res = max(res, num[i : i + 3])

        return "" if res == "0" else res

public class Solution {
    public String largestGoodInteger(String num) {
        String res = "";

        for (int i = 0; i < num.length() - 2; i++) {
            if (num.charAt(i) == num.charAt(i + 1) &&
                num.charAt(i) == num.charAt(i + 2)) {
                String curr = num.substring(i, i + 3);
                if (curr.compareTo(res) > 0) {
                    res = curr;
                }
            }
        }

        return res;
    }
}

class Solution {
public:
    string largestGoodInteger(string num) {
        string res = "0";

        for (int i = 0; i < num.length() - 2; i++) {
            if (num[i] == num[i + 1] && num[i] == num[i + 2]) {
                res = max(res, num.substr(i, 3));
            }
        }

        return res == "0" ? "" : res;
    }
};

class Solution {
    /**
     * @param {string} num
     * @return {string}
     */
    largestGoodInteger(num) {
        let res = '0';

        for (let i = 0; i < num.length - 2; i++) {
            if (num[i] === num[i + 1] && num[i] === num[i + 2]) {
                res = res > num.slice(i, i + 3) ? res : num.slice(i, i + 3);
            }
        }

        return res === '0' ? '' : res;
    }
}

public class Solution {
    public string LargestGoodInteger(string num) {
        string res = "0";

        for (int i = 0; i < num.Length - 2; i++) {
            if (num[i] == num[i + 1] && num[i] == num[i + 2]) {
                string tmp = num.Substring(i, 3);
                if (string.Compare(tmp, res) > 0) {
                    res = tmp;
                }
            }
        }

        return res == "0" ? "" : res;
    }
}

func largestGoodInteger(num string) string {
    res := "0"

    for i := 0; i < len(num)-2; i++ {
        if num[i] == num[i+1] && num[i] == num[i+2] {
            tmp := num[i : i+3]
            if tmp > res {
                res = tmp
            }
        }
    }

    if res == "0" {
        return ""
    }
    return res
}

class Solution {
    fun largestGoodInteger(num: String): String {
        var res = "0"

        for (i in 0 until num.length - 2) {
            if (num[i] == num[i + 1] && num[i] == num[i + 2]) {
                val tmp = num.substring(i, i + 3)
                if (tmp > res) {
                    res = tmp
                }
            }
        }

        return if (res == "0") "" else res
    }
}

class Solution {
    func largestGoodInteger(_ num: String) -> String {
        var res = "0"
        let chars = Array(num)

        for i in 0..<(chars.count - 2) {
            if chars[i] == chars[i + 1] && chars[i] == chars[i + 2] {
                let tmp = String(chars[i..<(i + 3)])
                if tmp > res {
                    res = tmp
                }
            }
        }

        return res == "0" ? "" : res
    }
}

impl Solution {
    pub fn largest_good_integer(num: String) -> String {
        let bytes = num.as_bytes();
        let mut res = String::new();

        for i in 0..bytes.len() - 2 {
            if bytes[i] == bytes[i + 1] && bytes[i] == bytes[i + 2] {
                let curr = &num[i..i + 3];
                if curr > res.as_str() {
                    res = curr.to_string();
                }
            }
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

3. Iteration (Optimal)

Intuition

We can optimize further by observing that we only need to track the digit itself, not the entire 3-character substring. Since all good integers are formed by repeating a single digit three times, we just need to find the largest digit that appears three times consecutively. At the end, we can construct the result by repeating that digit three times.

Algorithm

Initialize res to -1 to indicate no good integer found yet.
Iterate through the string, checking each window of size 3:
- If three consecutive characters are the same, extract the digit value and update res if it is larger.
If res is still -1, return an empty string. Otherwise, return the digit repeated three times.

class Solution:
    def largestGoodInteger(self, num: str) -> str:
        res = -1

        for i in range(len(num) - 2):
            if num[i] == num[i + 1] == num[i + 2]:
                res = max(res, int(num[i]))
        return str(res) * 3 if res != -1 else ""

public class Solution {
    public String largestGoodInteger(String num) {
        int res = -1;

        for (int i = 0; i < num.length() - 2; i++) {
            if (num.charAt(i) == num.charAt(i + 1) &&
                num.charAt(i) == num.charAt(i + 2)) {
                res = Math.max(res, num.charAt(i) - '0');
            }
        }

        return res != -1 ? String.valueOf(res).repeat(3) : "";
    }
}

class Solution {
public:
    string largestGoodInteger(string num) {
        int res = -1;

        for (int i = 0; i < num.length() - 2; i++) {
            if (num[i] == num[i + 1] && num[i] == num[i + 2]) {
                res = max(res, num[i] - '0');
            }
        }

        return res != -1 ? string(3, res + '0') : "";
    }
};

class Solution {
    /**
     * @param {string} num
     * @return {string}
     */
    largestGoodInteger(num) {
        let res = -1;

        for (let i = 0; i < num.length - 2; i++) {
            if (num[i] === num[i + 1] && num[i] === num[i + 2]) {
                res = Math.max(res, Number(num[i]));
            }
        }

        return res !== -1 ? String(res).repeat(3) : '';
    }
}

public class Solution {
    public string LargestGoodInteger(string num) {
        int res = -1;

        for (int i = 0; i < num.Length - 2; i++) {
            if (num[i] == num[i + 1] && num[i] == num[i + 2]) {
                res = Math.Max(res, num[i] - '0');
            }
        }

        return res == -1 ? "" : new string((char)(res + '0'), 3);
    }
}

class Solution {
    fun largestGoodInteger(num: String): String {
        var res = -1

        for (i in 0 until num.length - 2) {
            if (num[i] == num[i + 1] && num[i] == num[i + 2]) {
                res = maxOf(res, num[i] - '0')
            }
        }

        return if (res == -1) "" else res.toString().repeat(3)
    }
}

class Solution {
    func largestGoodInteger(_ num: String) -> String {
        var res = -1
        let chars = Array(num)

        for i in 0..<(chars.count - 2) {
            if chars[i] == chars[i + 1] && chars[i] == chars[i + 2] {
                let digit = Int(String(chars[i]))!
                res = max(res, digit)
            }
        }

        return res == -1 ? "" : String(repeating: String(res), count: 3)
    }
}

impl Solution {
    pub fn largest_good_integer(num: String) -> String {
        let bytes = num.as_bytes();
        let mut res: i32 = -1;

        for i in 0..bytes.len() - 2 {
            if bytes[i] == bytes[i + 1] && bytes[i] == bytes[i + 2] {
                let digit = (bytes[i] - b'0') as i32;
                res = res.max(digit);
            }
        }

        if res == -1 {
            String::new()
        } else {
            std::iter::repeat(char::from(b'0' + res as u8))
                .take(3)
                .collect()
        }
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Forgetting That "000" Is a Valid Good Integer

The problem asks for the largest good integer, but "000" is still a valid answer if it is the only one found. Initializing the result to an empty string and checking only for non-zero matches causes "000" to be incorrectly skipped. Handle "000" explicitly or use comparison logic that includes it.

Returning the Wrong Result When No Good Integer Exists

If no three consecutive identical digits exist in the string, the answer should be an empty string. Returning "0", a default numeric value, or the last partial match leads to wrong answers. Always track whether any valid match was found before returning.