Teaching Kids Programming – Largest 3-Same-Digit Number in String

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

Hints:
We can sequentially check if 999, 888, 777, … 000 exists in num in that order. The first to be found is the maximum good integer.
If we cannot find any of the above integers, we return an empty string “”.

Largest 3-Same-Digit Number in String

There are only 10 possible 3-same-digit number which are (000, 111, 222…). We can check backwards from the largest 999 to the smallest 000. Once we have found the substring appearing in the string, that is the answer (the largest 3-same-digit).

1
2
3
4
5
6

class Solution:
    def largestGoodInteger(self, num: str) -> str:
        for i in range(9, -1, -1):
            if str(i)*3 in num:
                return str(i)*3
        return ""

class Solution:
    def largestGoodInteger(self, num: str) -> str:
        for i in range(9, -1, -1):
            if str(i)*3 in num:
                return str(i)*3
        return ""

The time complexity is O(N). We assume in Python the substring check is O(N) time where N is the longer string. For more details check the string KMP algorithm. The outer loop from 9 to 0 is constant time. The space complexity is O(1) constant.

Another approach is to iterate the substring of 3 and then check if it contains only 1 unique digit. O(N) time / O(1) space. We use a set to check if the substring has only 1 unique digit but it is still O(1) space due to the substring is length of 3.

1
2
3
4
5
6
7
8

class Solution:
    def largestGoodInteger(self, num: str) -> str:
        n = len(num)
        ans = ""
        for i in range(n - 2):
            if len(set(num[i:i+3])) == 1:
                ans = max(ans, num[i:i+3])
        return ans

class Solution:
    def largestGoodInteger(self, num: str) -> str:
        n = len(num)
        ans = ""
        for i in range(n - 2):
            if len(set(num[i:i+3])) == 1:
                ans = max(ans, num[i:i+3])
        return ans

–EOF (The Ultimate Computing & Technology Blog) —