algoadvance

You are given a string num representing a large integer. Return the largest-valued 3-digit combination that consists of the same digit. If no such combination exists, return an empty string.

Clarifying Questions

  1. Input Format: Is the input always a non-empty string composed exclusively of digits?
    • Yes, the input string num is non-empty and contains only digit characters.
  2. Output: Should the output be an empty string if no 3-same-digit number is found?
    • Yes, if no such combination exists, return an empty string.
  3. Maximum Length of Input: What is the maximum length of the input string?
    • The maximum length isn’t explicitly mentioned, but you can assume a typical competitive programming constraint where the length could be up to (10^5).

Strategy

To solve this problem, we will perform the following steps:

  1. Initialize a Variable: We’ll keep track of the largest 3-same-digit number found while iterating through the string.
  2. Iterate Through the String: We’ll loop through the string and check every possible contiguous sequence of 3 characters.
  3. Check for 3-Same-Digit Combination: For each such sequence, we’ll check if all three characters are the same.
  4. Compare and Update: If we find a valid 3-same-digit number, we’ll compare it with the currently stored largest value and update if it’s larger.
  5. Edge Cases: Consider edge cases such as strings shorter than 3 characters, in which we would directly return an empty string.

Code

Here’s how you can implement this strategy in Python:

def largest_good_integer(num):
    largest = ""
    n = len(num)
    
    for i in range(n - 2):
        if num[i] == num[i+1] == num[i+2]:
            candidate = num[i:i+3]
            if candidate > largest:
                largest = candidate

    return largest

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

Time Complexity

The time complexity of the solution is (O(n)), where (n) is the length of the input string. This is because we are iterating through the string once and performing constant time checks for each set of three characters.

Space Complexity

The space complexity is (O(1)) since we are using a constant amount of extra space for the largest variable and a few temporary variables.

Try our interview co-pilot at AlgoAdvance.com