Solution Explanation: Finding the Largest 3-Same-Digit Number

The problem asks to find the largest substring of length 3 within a given string num where all three characters are identical. The solution employs a straightforward iterative approach.

Approach:

The algorithm iterates through digits from 9 down to 0. For each digit, it constructs a string of length 3 consisting of that digit ("777", "666", etc.). It then checks if this string is a substring of the input num. If found, it immediately returns this substring as it's the largest good integer found so far. If the loop completes without finding any such substring, it returns an empty string, indicating no good integer exists.

Time Complexity Analysis:

The outer loop iterates at most 10 times (digits 0-9). The contains or find operation within the loop (depending on the programming language used) has a time complexity of O(n), where n is the length of the input string num. Therefore, the overall time complexity is O(10n), which simplifies to O(n) as constant factors are ignored in Big O notation.

Space Complexity Analysis:

The algorithm uses a constant amount of extra space to store the current digit string and other intermediate variables. Therefore, the space complexity is O(1).

Code Examples in Different Languages:

The following code snippets demonstrate the solution in several programming languages:

Python:

class Solution:
    def largestGoodInteger(self, num: str) -> str:
        for i in range(9, -1, -1):
            s = str(i) * 3  # Create a string of three identical digits
            if s in num:     # Check if it's a substring of num
                return s
        return ""

Java:

class Solution {
    public String largestGoodInteger(String num) {
        for (int i = 9; i >= 0; i--) {
            String s = String.valueOf(i).repeat(3); // Java 11+ repeat method
            if (num.contains(s)) {
                return s;
            }
        }
        return "";
    }
}

C++:

class Solution {
public:
    string largestGoodInteger(string num) {
        for (char i = '9'; i >= '0'; --i) {
            string s(3, i); // Create a string of three identical characters
            if (num.find(s) != string::npos) { // Check for substring
                return s;
            }
        }
        return "";
    }
};

JavaScript:

/**
 * @param {string} num
 * @return {string}
 */
var largestGoodInteger = function(num) {
    for (let i = 9; i >= 0; i--) {
        let s = `${i}${i}${i}`; // Create a string of three identical digits
        if (num.includes(s)) {  //Check if it's a substring
            return s;
        }
    }
    return "";
};

Go:

func largestGoodInteger(num string) string {
	for i := 9; i >= 0; i-- {
		s := strings.Repeat(strconv.Itoa(i), 3) // Create a string of three identical digits
		if strings.Contains(num, s) {           // Check if it's a substring
			return s
		}
	}
	return ""
}
 

All these code examples follow the same basic algorithm, differing only in syntax and specific string manipulation functions. They all achieve a linear time complexity and constant space complexity.