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.
1#include <iostream>
2#include <string>
3using namespace std;
4
5string largestGoodInteger(string num) {
6 string maxGood = "";
7 for (int i = 0; i <= num.size() - 3; ++i) {
8 if (num[i] == num[i + 1] && num[i + 1] == num[i + 2]) {
9 string curr = num.substr(i, 3);
10 if (curr > maxGood) {
11 maxGood = curr;
12 }
13 }
14 }
15 return maxGood;
16}
17
18int main() {
19 string num = "6777133339";
20 cout << largestGoodInteger(num) << endl;
21 return 0;
22}The C++ solution iterates over each possible starting point for a 3-character substring, checking if the characters are identical. If a good integer is found, it compares it with the currently found maximum using string comparison, since strings can be compared lexicographically in C++.
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
public class Solution {
public string LargestGoodIntegerOptimized(string num) {
string maxGood = "";
for (int i = 0; i <= num.Length - 3; i++) {
if (num[i] == num[i+1] && num[i+1] == num[i+2]) {
if (num[i] == '9') return "999";
string curr = num.Substring(i, 3);
if (curr.CompareTo(maxGood) > 0) {
maxGood = curr;
}
}
}
return maxGood;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.LargestGoodIntegerOptimized("798939999"));
}
}C#'s optimized approach declutters execution where '999' is an early answer, thus experimenting with a quick-return case reduces operational times accordingly.