Jobs

Interviews

Discussions

Largest 3-Same-Digit Number in String

Easy

Asked by:

17 views

Topics:

Strings

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.

Try coding it in LeetCode

Largest 3-Same-Digit Number in String

Easy

Asked by:

17 views

Topics:

Strings

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string `num` contain characters other than digits?
What should I return if there is no 3-same-digit number in the string?
If multiple 3-same-digit numbers exist, should I return the largest one, and what determines 'largest' (e.g., numerical value of the digit)?
What is the maximum length of the input string `num`?
Is it possible for the input string `num` to be empty or null?

Brute Force Solution

Approach

The brute force method in this case means checking every possible group of three digits next to each other in the string. We look at each such group and see if all three digits are the same, and keep track of the largest such group we find.

Here's how the algorithm would work step-by-step:

Go through the string from the beginning, looking at each group of three consecutive digits.
For each group of three, check if all the digits are the same.
If they are the same, remember that group of three digits.
If we find a group of three that's larger than the one we remembered earlier, then forget the old one and remember the new larger one.
Once we've checked all possible groups of three, the one we remembered at the end is the answer.

Code Implementation

def find_largest_3_same_digit_number(number_string):
    largest_3_same_digits = ""

    for index in range(len(number_string) - 2):
        # Check every possible group of three digits

        group_of_three = number_string[index:index + 3]

        #If the characters in the substring are all equal
        if group_of_three[0] == group_of_three[1] == group_of_three[2]:
            #Convert the current substring and the largest one seen so far to integers and perform a comparison
            if largest_3_same_digits == "" or int(group_of_three) > int(largest_3_same_digits):

                largest_3_same_digits = group_of_three

    return largest_3_same_digits

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of length n, examining each group of three consecutive digits. For each group, it performs a constant time comparison to check if the digits are the same. Because we visit each index once and perform a constant amount of work at each index, the overall time complexity is O(n).

Space Complexity

O(1) – The described brute force algorithm only needs to store the largest 3-same-digit number found so far, which can be represented as a string or integer and its corresponding start index. These variables consume a constant amount of space irrespective of the input string's length, N. Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

The best way to find the largest same-digit number is to check each possible three-digit sequence in the input string and keep track of the largest one seen so far. We can efficiently update the largest same-digit number by directly comparing the numerical values of the digits we find.

Here's how the algorithm would work step-by-step:

Go through the string from beginning to end, looking at each group of three digits in a row.
For each group of three digits, check if all three digits are the same. If they aren't, move to the next group.
If the three digits are the same, see if this number is bigger than the largest same-digit number you've found so far. To do this, just compare the value of the digit. For instance, 555 is bigger than 444.
If the new number is bigger, remember it as the largest one.
After checking all the groups of three digits, if you found a largest same-digit number, that's your answer. If you didn't find any, it means there wasn't any same-digit number in the string, so the answer is an empty string.

Code Implementation

def largest_3_same_digit_number(number):
    largest_number = ""

    for i in range(len(number) - 2):
        # Extract a sequence of 3 digits.
        three_digit_sequence = number[i:i+3]

        # Check if all 3 digits are the same
        if three_digit_sequence[0] == three_digit_sequence[1] == three_digit_sequence[2]:

            # Update largest number if needed. Converting to int for comparison.
            if largest_number == "" or int(three_digit_sequence[0]) > int(largest_number[0]):
                largest_number = three_digit_sequence

    return largest_number

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string once, examining each group of three consecutive digits. For each position in the string, it performs a constant amount of work: checking if the three digits are the same and, if so, comparing the digit to the current largest. Therefore, the time complexity is directly proportional to the length of the string (n), making it O(n).

Space Complexity

O(1) – The provided algorithm iterates through the string and keeps track of the largest 3-same-digit number found so far. It uses a constant amount of extra space to store the largest digit found (if any) and potentially some temporary variables for comparison during the string traversal. The space used does not depend on the input string's length N. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty string input	Return an empty string immediately as there are no digits to form a 3-same-digit number.
String length less than 3	Return an empty string since a 3-same-digit number cannot be formed.
String contains non-digit characters	The solution should only process digit characters and ignore any non-digit characters encountered.
String contains no 3-same-digit numbers	Return an empty string to indicate that no such number was found.
Multiple 3-same-digit numbers exist; find the largest	The solution should iterate through all possible 3-same-digit numbers and return the largest one encountered.
String contains only one type of digit, repeated fewer than 3 times	Return an empty string as the condition for 3 same digits is not met.
String begins with leading zeros	Handle leading zeros correctly, e.g., '000123' should potentially return '000' if it's the largest.
Very long input string	The solution should iterate efficiently through the string to avoid time complexity issues.

Empty string input

How to Handle:

Return an empty string immediately as there are no digits to form a 3-same-digit number.

String length less than 3

How to Handle:

Return an empty string since a 3-same-digit number cannot be formed.

String contains non-digit characters

How to Handle:

The solution should only process digit characters and ignore any non-digit characters encountered.

String contains no 3-same-digit numbers

How to Handle:

Return an empty string to indicate that no such number was found.

Multiple 3-same-digit numbers exist; find the largest

How to Handle:

The solution should iterate through all possible 3-same-digit numbers and return the largest one encountered.

String contains only one type of digit, repeated fewer than 3 times

How to Handle:

Return an empty string as the condition for 3 same digits is not met.

String begins with leading zeros

How to Handle:

Handle leading zeros correctly, e.g., '000123' should potentially return '000' if it's the largest.

Very long input string

How to Handle:

The solution should iterate efficiently through the string to avoid time complexity issues.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string `num` contain characters other than digits?
What should I return if there is no 3-same-digit number in the string?
If multiple 3-same-digit numbers exist, should I return the largest one, and what determines 'largest' (e.g., numerical value of the digit)?
What is the maximum length of the input string `num`?
Is it possible for the input string `num` to be empty or null?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Go through the string from the beginning, looking at each group of three consecutive digits.
For each group of three, check if all the digits are the same.
If they are the same, remember that group of three digits.
If we find a group of three that's larger than the one we remembered earlier, then forget the old one and remember the new larger one.
Once we've checked all possible groups of three, the one we remembered at the end is the answer.

Code Implementation

def find_largest_3_same_digit_number(number_string):
    largest_3_same_digits = ""

    for index in range(len(number_string) - 2):
        # Check every possible group of three digits

        group_of_three = number_string[index:index + 3]

        #If the characters in the substring are all equal
        if group_of_three[0] == group_of_three[1] == group_of_three[2]:
            #Convert the current substring and the largest one seen so far to integers and perform a comparison
            if largest_3_same_digits == "" or int(group_of_three) > int(largest_3_same_digits):

                largest_3_same_digits = group_of_three

    return largest_3_same_digits

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Go through the string from beginning to end, looking at each group of three digits in a row.
For each group of three digits, check if all three digits are the same. If they aren't, move to the next group.
If the three digits are the same, see if this number is bigger than the largest same-digit number you've found so far. To do this, just compare the value of the digit. For instance, 555 is bigger than 444.
If the new number is bigger, remember it as the largest one.
After checking all the groups of three digits, if you found a largest same-digit number, that's your answer. If you didn't find any, it means there wasn't any same-digit number in the string, so the answer is an empty string.

Code Implementation

def largest_3_same_digit_number(number):
    largest_number = ""

    for i in range(len(number) - 2):
        # Extract a sequence of 3 digits.
        three_digit_sequence = number[i:i+3]

        # Check if all 3 digits are the same
        if three_digit_sequence[0] == three_digit_sequence[1] == three_digit_sequence[2]:

            # Update largest number if needed. Converting to int for comparison.
            if largest_number == "" or int(three_digit_sequence[0]) > int(largest_number[0]):
                largest_number = three_digit_sequence

    return largest_number

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty string input	Return an empty string immediately as there are no digits to form a 3-same-digit number.
String length less than 3	Return an empty string since a 3-same-digit number cannot be formed.
String contains non-digit characters	The solution should only process digit characters and ignore any non-digit characters encountered.
String contains no 3-same-digit numbers	Return an empty string to indicate that no such number was found.
Multiple 3-same-digit numbers exist; find the largest	The solution should iterate through all possible 3-same-digit numbers and return the largest one encountered.
String contains only one type of digit, repeated fewer than 3 times	Return an empty string as the condition for 3 same digits is not met.
String begins with leading zeros	Handle leading zeros correctly, e.g., '000123' should potentially return '000' if it's the largest.
Very long input string	The solution should iterate efficiently through the string to avoid time complexity issues.

Empty string input

How to Handle:

Return an empty string immediately as there are no digits to form a 3-same-digit number.

String length less than 3

How to Handle:

Return an empty string since a 3-same-digit number cannot be formed.

String contains non-digit characters

How to Handle:

The solution should only process digit characters and ignore any non-digit characters encountered.

String contains no 3-same-digit numbers

How to Handle:

Return an empty string to indicate that no such number was found.

Multiple 3-same-digit numbers exist; find the largest

How to Handle:

The solution should iterate through all possible 3-same-digit numbers and return the largest one encountered.

String contains only one type of digit, repeated fewer than 3 times

How to Handle:

Return an empty string as the condition for 3 same digits is not met.

String begins with leading zeros

How to Handle:

Handle leading zeros correctly, e.g., '000123' should potentially return '000' if it's the largest.

Very long input string

How to Handle:

The solution should iterate efficiently through the string to avoid time complexity issues.