algoadvance

Leetcode 2264. Largest 3

Problem Statement

Given a string s representing a number, you need to find the largest three-same-digit number in the given string. A three-same-digit number is a sequence of the same digit appearing three times consecutively. Return that largest number as a string. If there is no such number, return an empty string.

Clarifying Questions

1. Input Constraints:
   • What is the length range of the input string s?
   • Are there any characters other than digits in the string?

   Clarification:

   • The length of the input string s can be up to 10^5.
   • The string s will only contain numeric digits (0-9).
2. Output Specifications:
   • The output should be the largest three-same-digit number in the string.
   • If no such sequence exists, return an empty string.

Strategy

1. Traverse the String:
   • We will traverse the string while checking for any sequence of three consecutive same digits.
2. Compare and Store:
   • Every time we encounter a sequence of three same digits, we need to compare it with the previously found sequence to ensure we keep the largest one.
3. Edge Cases:
   • Handle cases where the string is less than 3 characters long.
   • Handle edge cases where there are no such three-same-digit sequences in the string.

Code

#include <iostream>
#include <string>
using namespace std;

string largestThreeSameDigitNumber(string s) {
    // Initialize the result as an empty string
    string result = "";
    int n = s.length();
    
    for (int i = 0; i < n - 2; i++) {
        if (s[i] == s[i+1] && s[i] == s[i+2]) {
            string current = s.substr(i, 3);
            if (result == "" || current > result) {
                result = current;
            }
        }
    }
    
    return result;
}

int main() {
    // Test cases
    cout << largestThreeSameDigitNumber("6777133339") << endl; // Output: "777"
    cout << largestThreeSameDigitNumber("2300019") << endl;    // Output: "000"
    cout << largestThreeSameDigitNumber("42352338") << endl;   // Output: ""

    return 0;
}

Time Complexity

• Time Complexity: (O(n))
  • We are making a single pass through the string to check for three-same-digit sequences. This results in a linear time complexity (O(n)), where (n) is the length of the string.
• Space Complexity: (O(1))
  • We are using a constant amount of space to store the result, hence the space complexity is (O(1)).

Feel free to ask for further clarifications or additional test cases!

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?