Leetcode 2264: Largest 3-Same-Digit Number in String

Input: You are given a string `num` representing a large integer.

Example: num = "98711111234"

Constraints:

• 3 <= num.length <= 1000

• num only consists of digits.

Output: Return the largest good integer as a string. If no such integer exists, return an empty string.

Example: Output: "111"

Constraints:

Goal: The goal is to find the maximum substring of length 3 that consists of only one unique digit.

Steps:

• Iterate through the string starting from index 2 to check all possible substrings of length 3.

• For each substring, check if all characters are the same.

• If a valid substring is found, compare it with the current maximum substring to keep the largest.

• Return the largest valid substring or an empty string if no such substring is found.

Goal: The input string `num` has a length between 3 and 1000, consisting only of digits.

Steps:

• The string `num` will always have a length of at least 3.

• The string only contains digits.

Assumptions:

• The string `num` will not be empty, as its length is always at least 3.

• Input: num = "98711111234"

• Explanation: In this case, the valid good integers are '111'. The largest good integer is '111', so the output is '111'.

• Input: num = "223335"

• Explanation: Here, the good integers are '333' and '222'. The largest good integer is '333', so the output is '333'.

• Input: num = "12345"

• Explanation: There are no substrings of length 3 that consist of only one unique digit. Therefore, the output is an empty string.

Approach: We will iterate through the string and check for substrings of length 3. If all the characters in the substring are the same, we will check if it's the largest one found so far.

Observations:

• We need to consider every substring of length 3 in the given string.

• The condition to check for a 'good' integer is simple: all characters in the substring must be the same.

• We can use a sliding window approach to check every substring of length 3 in one pass through the string.

Steps:

• Initialize a variable to store the largest good integer found, starting with an empty string.

• Iterate through the string from index 2 to the end.

• For each position, check if the previous two characters are the same as the current character (forming a valid 'good' integer).

• If the substring is valid and greater than the current largest, update the largest value.

• Return the largest good integer or an empty string if no such integer exists.

Empty Inputs:

• The string `num` is guaranteed to have a length of at least 3, so there are no empty inputs.

Large Inputs:

• The solution should handle large strings efficiently, especially up to 1000 characters.

Special Values:

• Consider strings that have repeated digits like '000' or strings with no valid good integers.

Constraints:

• The solution should work within the time complexity constraints of strings with lengths up to 1000.

string largestGoodInteger(string num) {
    char res = 0;
for(int i = 2; i < num.size(); ++i)
    if (num[i] == num[i - 1] && num[i] == num[i - 2])
        res = max(res, num[i]);
return res == 0 ? "" : string(3, res);
}

1 : Function Declaration

string largestGoodInteger(string num) {

The function `largestGoodInteger` takes a string `num` as input and returns the largest good integer, which is a substring of three consecutive identical digits.

2 : Variable Initialization

    char res = 0;

The variable `res` is initialized to 0. It will hold the largest digit found that forms a good integer.

3 : For Loop

for(int i = 2; i < num.size(); ++i)

A for loop starts from index 2, iterating through the string `num` from the third character onward. This is to check for triplets of consecutive characters.

4 : Condition Check

    if (num[i] == num[i - 1] && num[i] == num[i - 2])

This condition checks if the current character and the previous two characters in the string are identical, indicating a good integer (a substring of three consecutive identical digits).

5 : Update Largest Good Integer

        res = max(res, num[i]);

If a good integer is found (three consecutive identical digits), the maximum of the current largest good integer (`res`) and the new character `num[i]` is stored in `res`.

6 : Return Result

return res == 0 ? "" : string(3, res);

After the loop, if no good integer was found (`res == 0`), the function returns an empty string. Otherwise, it returns a string consisting of the largest good integer, repeated three times.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n) because we check each substring of length 3 once.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1) because we only need a constant amount of space for tracking the largest good integer.

Leetcode 2264: Largest 3-Same-Digit Number in String

Explore →