Google Interview Question
SDE1sCountry: United States
O(n) time complexity, O(1) space
#include <iostream>
using namespace std;
string FindLargestSubString(string s)
{
int length = s.length();
int i = 0;
int j = i+1;
while(j<length)
{
if(s[j] > s[i])
{
i = j;
j = j+1;
}
else if(s[j] < s[i])
{
j = j+1;
}
else
{
int k = i;
int l = j;
while(l < length)
{
if(s[k] > s[i])
{
i = k;
j = l;
break;
}
else if(s[l] > s[i])
{
i = l;
j = l+1;
break;
}
else if(s[k] > s[l])
{
j = l+1;
break;
}
else if(s[k] < s[l])
{
i = j;
j = l+1;
break;
}
else
{
l++;
k++;
}
}
if(l == length)
{
j = l;
break;
}
}
}
return s.substr(i);
}
int main() {
string s;
cin>>s;
cout<<FindLargestSubString(s);
}
- lxfuhuo January 08, 2018