Problem

Solution

Intuition

This problem requires us to find a substring of 3 matching numbers. We need to traverse the array at least once to see every number and ensure we have found the highest of possible substrings. We need to track how many consecutive numbers that have been seen are similar and if there are three, we store this value.

Approach

We traverse the array with a counter initialized to 1 to symbolize the current number of matching numbers in the current substring. We then iterate through while incrementing the count if the next number is the same. Once we reach three, we store the largest of identified substrings. If we find a number that is no longer the same, we reset the counter and continue incrementing.

Complexity

• Time complexity: $O(n)$ as we iterate through the string once doing a constant time operation in each iteration.

• Space complexity: $O(1)$ as we only store the result which has a maximum length of 3.

Code

class Solution:
    def largestGoodInteger(self, num: str) -> str:
        res = '' 
        cnt = 1
        for i in range(1, len(num)):
            if num[i] == num[i-1]:
                cnt+=1
            else:
                cnt = 1
            if cnt == 3:
                res = max(res, num[i] * 3)
                
        return res