Largest 3 Same Digit Number In String - Leetcode Solution

Problem statement: Given a string str, find the largest 3 digit number that can be formed by its digits.

Example 1: Input: "abc999xyz" Output: 999 Explanation: The largest 3 digit number that can be formed using the digits in the string 'abc999xyz' is 999.

Example 2: Input: "a1b2c3d4e5f6g7h8i9j0" Output: 987 Explanation: The largest 3 digit number that can be formed using the digits in the string 'a1b2c3d4e5f6g7h8i9j0' is 987.

Solution: To solve this problem, we will traverse the string from left to right and keep track of all the three digit numbers in the string. We will compare these numbers with each other and keep only the largest one.

Algorithm:

1. Create an empty list to store all the three digit numbers in the string.
2. Traverse the string from left to right.
3. If a character is a digit, check the next two characters to form a three digit number.
4. If a three digit number is found, append it to the list created in step 1.
5. After the traversal is complete, sort the list in descending order.
6. Return the first element of the list as it will be the largest three digit number.

Code:

def largest_three_digit_number_in_string(string):
    numbers_list = []
    for i in range(len(string)-2):
        if string[i].isdigit():
            num = int(string[i:i+3])
            numbers_list.append(num)
    numbers_list.sort(reverse=True)
    return numbers_list[0] if numbers_list else None

Explanation: We have defined a function named largest_three_digit_number_in_string which takes a string as an input parameter. We have created an empty list numbers_list to store all the three digit numbers in the string. We have then traversed the string using a for loop from 0 to len(string)-2. The reason for using len(string)-2 instead of len(string)-3 is that we need to check 3 characters at a time, so we don't want to run into an index error.

Within the for loop, we check if the current character is a digit. If it is, then we take the next two characters to create a three digit number and append it to the numbers_list. Once the for loop is complete, we sort the numbers_list in descending order.

Finally, we return the first element of the list, which will be the largest three digit number that can be formed from the given input string. We have also added a condition to check if the list is empty, in which case we return None.

Time complexity: The time complexity of this solution is O(n log n) due to the sorting of the list.

Space complexity: The space complexity of this solution is O(k), where k is the number of three digit numbers in the input string.

1