Sponsored
Sponsored
This approach involves iterating through the string, checking every possible substring of length 3 to see if it consists of the same character. If it does, keep track of the largest such substring found.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), constant space is used.
1def largestGoodInteger(num: str) -> str:
2 max_good = ""
3 for i in range(len(num) - 2):
4 if num[i] == num[i+1] == num[i+2]:
5 curr = num[i:i+3]
6 if curr > max_good:
7 max_good = curr
8 return max_good
9
10num = "6777133339"
11print(largestGoodInteger(num))The Python solution uses string slicing and comparison to find and update the largest good integer within the loop. It checks each substring of length three for identical characters, compares and finds the maximum.
This approach builds upon the basic iteration method, with an early termination feature if the maximum possible good integer ("999") is found. This can optimize cases where digits towards the start of the string quickly identify the upper bound, reducing unnecessary checks.
Time Complexity: Less than O(n) in the best case if "999" is early.
Space Complexity: O(1).
1#include <string>
using namespace std;
string largestGoodIntegerOptimized(string num) {
string maxGood = "";
for (int i = 0; i <= num.size() - 3; ++i) {
if (num[i] == num[i + 1] && num[i + 1] == num[i + 2]) {
if (num[i] == '9') return "999";
string curr = num.substr(i, 3);
if (curr > maxGood) {
maxGood = curr;
}
}
}
return maxGood;
}
int main() {
string num = "7779133339";
cout << largestGoodIntegerOptimized(num) << endl;
return 0;
}In C++, the optimized approach leverages an early exit condition for the string form '999'. This substantially shortens processing time for certain inputs.