Find the maximum 3 same digits in the string

introduce

Give you a string num , Represents a large integer . If an integer satisfies all of the following conditions , The integer is considered to be a High quality integer ：

• The integer is num One length of the is 3 Of Substring .
• The integer is repeated by a unique number 3 Secondary composition .

Returns... As a string The largest good integer . If there is no integer that meets the requirements , Then return an empty string “” .

Be careful ：

• Substring Is a sequence of consecutive characters in a string .
• num Or high-quality integers may exist Leading zero .

Example

Example 1：

Input ：num = “6777133339”
Output ：“777”
explain ：num There are two high-quality integers in ：“777” and “333” .
“777” It's the biggest one , So back “777” .

Example 2：

Input ：num = “2300019”
Output ：“000”
explain ：“000” Is the only good integer .

Example 3：

Input ：num = “42352338”
Output ：“”
explain ： There is no length of 3 An integer consisting of only one unique number . therefore , There are no good integers .

solution

My god ~ Such a simple problem, the official should use enumeration method （ Enumerating string num All lengths in are 3 The string of , And record the substring with the largest value required by the symbol ）, It's a bit superfluous , I thought it would be faster to match the string directly , Anyway, a total of 9 Substring .

C++ Code ：

class Solution {
    
public:
    string largestGoodInteger(string num) {
    
        for(int i=9 ; i>=0;i--){
    
            string s(3,'0'+i);
            if(num.find(s)!= string::npos){
    
                return s; // If the string find If it is not empty, at least one is found （ Start with the biggest ）
            }
        }
        return "";
    }
};

Official enumeration

The official idea is to enumerate strings $\text{num}$ All lengths in are $3$ The string of , And record the substring that meets the requirements and has the largest corresponding value .

In particular , We use a string with an empty initial value $\text{res}$ To maintain the maximum number of matching substrings , At the same time, the traverse length from left to right is $3$ The starting subscript of the substring $i$, Every time we traverse to a new subscript $i$, We judge by substring $\text{num}[i..i+2]$ Whether it is composed of the same characters ： If yes, the substring meets the requirements , We will $\text{res}$ Updated to $\text{res}$ And the larger value of the substring （ Here, the size relationship of the string dictionary order is consistent with that of the corresponding integer ）; If not, do nothing .
Final , If there is a substring that meets the requirements , be $\text{res}$ That is, the substring with the largest corresponding value ; If it doesn't exist , be $\text{res}$ Is an empty string . So we go back to $\text{res}$ As the answer .

class Solution {
    
public:
    string largestGoodInteger(string num) {
    
        int n = num.size();
        string res;
        for (int i = 0; i < n - 2; ++i) {
    
            if (num[i] == num[i+1] && num[i+1] == num[i+2]) {
    
                res = max(res, num.substr(i, 3));
            }
        }
        return res;
    }
};

summary

The disadvantage of the official enumeration method is that it will loop whether you find it or not n-3 Time ,
That is, the best and worst time complexity are $O(n)$
, The space complexity is $O(1)$

And we go from 999 The best time complexity to start string matching is to find... The first time $O(1)$, The worst time complexity is $O(n^2)$（ Although there is no regulation find Efficiency of function , We will match each time ）, The space complexity is $O(1)$

Oh my god ！！ Careless, no flash , It's still the official force after analysis , Do not call the substring lookup function , The balance of time and space is achieved by enumerating directly , The enumeration method should be better than the official method when the string is disordered , But if the matching string appears in the early stage, the efficiency of my algorithm will be obviously improved , Each has its own merits