Largest 3-Same-Digit Number in String Interview Question for Amazon

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.

def largestGoodInteger(num: str) -> str:
    """Given a string num representing a large integer, return the maximum good integer as a string or an empty string """ if no such integer exists.

    A good integer meets the following conditions:
    - It is a substring of num with length 3.
    - It consists of only one unique digit.

    For example:
    largestGoodInteger("6777133339") == "777"
    largestGoodInteger("2300019") == "000"
    largestGoodInteger("42352338") == ""
    """
    ans = ""
    for i in range(len(num) - 2):
        sub = num[i:i+3]
        if len(set(sub)) == 1:
            if ans == "" or sub > ans:
                ans = sub
    return ans

# Brute force solution:
# Iterate through all substrings of length 3 and check if they are good integers.
# The maximum good integer is the largest good integer found.
# If no good integer is found, return an empty string.

# Optimal solution:
# Iterate through all substrings of length 3 and check if they are good integers.
# Keep track of the largest good integer found so far.
# If a larger good integer is found, update the largest good integer.
# If no good integer is found, return an empty string.

# Big O run-time analysis:
# The run-time complexity is O(n), where n is the length of the string num.
# This is because we iterate through all substrings of length 3, which takes O(n) time.

# Big O space usage analysis:
# The space complexity is O(1), because we only use a few variables to store the largest good integer and the current substring.

# Edge cases:
# If the string num is empty, return an empty string.
# If the string num has length less than 3, return an empty string.
# If the string num does not contain any good integers, return an empty string.
# If the string num contains multiple good integers, return the largest good integer.

# Example usage:
# print(largestGoodInteger("6777133339")) # "777"
# print(largestGoodInteger("2300019")) # "000"
# print(largestGoodInteger("42352338")) # ""

Brute Force Approach

The brute force solution involves iterating through all possible substrings of length 3 and checking if each substring consists of only one unique digit. If a substring meets this condition, we compare it with the current maximum good integer found so far and update the maximum if necessary. If no good integer is found, we return an empty string.

Optimal Solution

The optimal solution is the same as the brute force solution. The reason is that we must examine all possible substrings of length 3 to determine if they are "good integers". Therefore, there is no way to avoid this iteration. We maintain a variable to track the largest good integer found so far, updating it whenever a larger good integer is encountered.

Big O Run-time Analysis

The time complexity of the provided solution is O(n), where n is the length of the input string num. This is because the code iterates through the string once using a for loop, examining each substring of length 3. Within the loop, the operations performed (substring extraction, set creation to check for unique digits, and string comparison) take constant time. Thus, the overall time complexity is directly proportional to the length of the string.

Big O Space Usage Analysis

The space complexity of the solution is O(1), which means it uses a constant amount of extra space regardless of the input string's length. The variables used (ans, sub, and the loop variable i) consume a fixed amount of memory. The set(sub) operation creates a set with at most 3 elements, which is still considered constant space. Therefore, the space usage does not scale with the input size.

Edge Cases

Empty String: If the input string num is empty, the loop will not execute, and the function will return an empty string, which is the expected behavior.
String Length Less Than 3: If the length of num is less than 3, the loop will also not execute, and an empty string will be returned, as no good integer can exist.
No Good Integers: If the string contains no substrings of length 3 consisting of a single repeating digit, the ans variable will remain empty, and the function will correctly return an empty string.
Leading Zeroes: The code handles leading zeroes correctly. If a substring like "000" is encountered, it will be considered a valid good integer and compared with the current maximum. Since "000" is a valid string, it can potentially be the largest good integer if no other larger good integers are found.