## Google Interview Question for Software Engineers

Country: United States

Comment hidden because of low score. Click to expand.
2
of 2 vote

Let's use Failure function of KMP algorithm. First calculate it. Then iterate the array and each time get Failure[i] which is the end of the longest prefix that is suffix to the substring[0...i]
We check if next character a[i +1] is great than arr[Failure[i]+1].That's is the place where we have first unmatch.
In case it is greater, we have found the longest substring that is lexicographic great than our string S. Otherwise we continues to iterate the array with incremented i. Time complexity - O(n), space complexity O(n).

``````String longestSubstring(String str) {
int[] failure = new int[str.length()];
failure[0] = -1;
int i  = 1;
//compute failure function
while (i < str.length()) {
int cur = failure[i - 1];
while (str.charAt(i) != str.charAt(cur + 1)) {
if (cur != -1)
cur = failure[cur];
else
break;
}
if (str.charAt(i) == str.charAt(cur + 1)) {
failure[i] = cur + 1;
}
else
failure[i] = -1;
i++;
}
String res = null;
for (i = 1; i < str.length() - 1; i++) {
if (failure[i] == -1) {
if (str.charAt(0) < str.charAt(i)) {
res = str.substring(i);
break;
}
}
else {
if (str.charAt(failure[i] + 1) < str.charAt(i + 1)) {
res = str.substring(i - failure[i]);
break;
}
}
}
if (str.charAt(0) < str.charAt(i))
return str.substring(i);
return res;
}``````

Comment hidden because of low score. Click to expand.
0

Neat! Like it.

Comment hidden because of low score. Click to expand.
0

I like this solution but the code and run time can be reduced in half.

When you are calculating the failure function, you are already applying the pattern to itself. All you need to do is return from the failure function computation as soon as you find a character in the pattern that is greater than the corresponding one in the prefix. There is no need to apply the pattern to itself again in the second half of the code.

Comment hidden because of low score. Click to expand.
0
of 0 vote

public int calculateLongestSubstring(String a)
{
int max = 0;
for(int i = 1; i<a.length(); i++)
{
int temp = getMaxString(a,i);
max = (max>temp)?max:temp;
}

return max;
}

private int getMaxString(a,i)
{
int idx= i;
while(idx != a.length();a.get(idx-i)==a.get(idx)) idx++;

if(idx == a.length()) return 0;
if(a.get(idx-i) < a.get(i)) return a.length()-i;
return 0;

}

Worst case O(n^2) .

For O(n) you could modify the pattern matching algorithm to use kmp , to get all break points(a break point is first character for a substring which mismatches), compute using that. Ill come up with code for that later..

Comment hidden because of low score. Click to expand.
0
of 0 vote

Let's use Failure function of KMP algorithm. First calculate it. Then iterate the array and each time get Failure[i] which is the end of the longest prefix that is suffix to the substring[0...i]
We check if next character a[i +1] is great than arr[Failure[i]+1].That's is the place where we have first unmatch.
In case it is greater, we have found the longest substring that is lexicographic great than our string S. Otherwise we continues to iterate the array with incremented i. Time complexity - O(n), space complexity O(n).

Comment hidden because of low score. Click to expand.
0
of 0 vote

C implementation:

``````#include <string.h>
#include <stdio.h>
//prototypes
int compare(char str1[], char str2[], int len);
void printStr(char str[]);
void longest_largest_substring(char str[])
{
int length = strlen(str);
for (int i = 1; i < length; i++)
{
if (compare(str, &str[i], length - i) < 0)
{
printStr(&str[i]);
break;
}
}
}
int compare(char str1[], char str2[], int len)
{
for (int i = 0; i < len; i++)
{
if (str1[i] == str2[i])
{
continue;
}
else if (str1[i] > str2[i])
{
return 1;
}
else
{
return -1;
}
}
return 0;
}
void printStr(char str[])
{
while (*str != '\0')
{
printf("%c", *str);
str++;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class LongLexically
{
void findLongestLexically(string s)
{
for(int i= 0 ; i < s.Length ; i++)
{
if ((int)s.ElementAt(i) > (int)s.ElementAt(0))
{
Console.WriteLine (s.Substring(i, s.Length - i));
break;
}
}

}
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

C++, implementation, O(n)

``````void printLongestSubstringLexBigger(string str) {
int i, j;
bool found;

for (i = 1; i < str.size(); i++) {
found = false;
for (j = 0; i + j < str.size(); j++) {
if (str[j] > str[i + j]) {
i += j;
break;
} else if (str[j] < str[i + j]) {
found = true;
break;
}
}

if (found) {
cout << str.substr(i) << "\n";
break;
}
}
}``````

Comment hidden because of low score. Click to expand.
0

I believe that you can simplify this to

``````void printLongestSubstringLexBigger(const string &str) {
for (size_t i = 1; i < str.size(); i++) {
for (size_t j = 0; i + j < str.size(); j++) {
if (str[j] > str[i + j]) {
i += j;
break;
} else if (str[j] < str[i + j]) {
cout << str.substr(i) << endl;
return;
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0

That solves the problem, but it doesn't look like O(N).
Input string = "aa...aaa"(N times). You have (N-1) + (N-2) + ... +1, which is O(N^2).

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def longestSubstr(s):
for i in xrange(1, len(s)):
if s[i] > s[0]:
break

while i > 1 and s[i-1] == s[0]:
i -= 1

return s[i:]``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

abc -> bc
sst -> st
ssat -> t
dcbdcbx -> dcbx
dcbdcbax -> x

Comment hidden because of low score. Click to expand.
0
of 0 vote

dcbdcbx -> dcbx (Why x is not the answer here)
dcbdcbax -> x

Comment hidden because of low score. Click to expand.
1
of 1 vote

dcbx and x is lex bigger than dcbd... And dcbx is longer than x. So dcbx is longest substring in this problem.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````///////////////////////////////////////////////////////////////////////////////
// @file FindLongestLargerSubString.cxx
// @compile g++ -Wall -o FindLongestLargerSubString FindLongestLargerSubString
///////////////////////////////////////////////////////////////////////////////
#include <string.h>
#include <assert.h>
#include <iostream>
///////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////
using namespace std;
///////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////
// @function FindLongestLargerSubString
///////////////////////////////////////////////////////////////////////////////
// @decription Given a string S, print the longest substring P such that P > S
// lexicographically. You may assume that such substring exists.
///////////////////////////////////////////////////////////////////////////////
// @param pS const char* const - the input string [IN]
//
// @param rIdx reference to an unsigned int - upon return this will have the
// the index of the larger substring, unless such a substring does not exist,
// in which case it will be set to UINT_MAX; one consequence of this is
// the length of the input string, excluding the terminating character, must
// be no larger than UINT_MAX - 0x2
///////////////////////////////////////////////////////////////////////////////
// @return bool true if found, false otherwise
///////////////////////////////////////////////////////////////////////////////
// @performance O(n) in number of characters in pS
///////////////////////////////////////////////////////////////////////////////
bool FindLongestLargerSubString(const char* const pS, unsigned int& rIdx)
{
///////////////////////////////////////////////////////////////////////////
assert(pS);
///////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////
bool bRet = false;
///////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////
unsigned int nLen = strlen(pS);
///////////////////////////////////////////////////////////////////////////
// We are assured that such a substring, P, exists. Adopting the convention
// a string is also one of its substrings (akin to every set being its
// own subset), if P exists, then P != S. Why? Well, we are given that
// P > S (lexicographically), and S !> S. To satisfy this, S must be at
// least two characters long. Assert it.
//
// Note: even if caller does not abide by the contract of passing a
// string to us that has at least a lexicographically larger substring,
// we will assert if length of string is less than two characters, but
// also detect that no such substring exist.
///////////////////////////////////////////////////////////////////////////
if (nLen < 0x2) {
///////////////////////////////////////////////////////////////////////
cout << "\n\tBroken contract - input length < 2. Bailing!\n\n"
<< flush;
///////////////////////////////////////////////////////////////////////
assert(nLen > 0x1);
///////////////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////
rIdx = UINT_MAX;
///////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////
// Remember the beginning character.
///////////////////////////////////////////////////////////////////////////
char beginChar = pS[0x0];
///////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////
// We wish to remember the position, if it exists, of a character
// downstream that matches begin.
///////////////////////////////////////////////////////////////////////////
int matchBeginPos = 0x0;
///////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////
// Start from the second character in the string (we are assured that there
// is a second character - see comments above.
///////////////////////////////////////////////////////////////////////////
for (int idx = 0x1; idx < nLen; idx++) {
///////////////////////////////////////////////////////////////////////
if (matchBeginPos == 0x0) {
///////////////////////////////////////////////////////////////////
if (pS[idx] > beginChar) {
///////////////////////////////////////////////////////////////
// We are done
///////////////////////////////////////////////////////////////
rIdx = idx;
///////////////////////////////////////////////////////////////
break;
///////////////////////////////////////////////////////////////
} else if (pS[idx] == beginChar) {
///////////////////////////////////////////////////////////////
matchBeginPos = idx;
///////////////////////////////////////////////////////////////
} else {
///////////////////////////////////////////////////////////////
// Nothing to do.
///////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////
} else {
///////////////////////////////////////////////////////////////////
// Have already seen a character that matches beginChar
///////////////////////////////////////////////////////////////////
if (pS[idx] > pS[idx - matchBeginPos]) {
///////////////////////////////////////////////////////////////
// We are done. Have found it.
///////////////////////////////////////////////////////////////
rIdx = matchBeginPos;
///////////////////////////////////////////////////////////////
break;
///////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////
// If caller hasn't abided by contract of having at least one substring
// P > S lexicographically, then we indicate it with the return value.
///////////////////////////////////////////////////////////////////////////
if (rIdx < UINT_MAX) {
///////////////////////////////////////////////////////////////////////
bRet = true;
///////////////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////
return bRet;
///////////////////////////////////////////////////////////////////////////
}

///////////////////////////////////////////////////////////////////////////////
// @function main
///////////////////////////////////////////////////////////////////////////////
// @decription the entry-point into our program
///////////////////////////////////////////////////////////////////////////////
// @param argc int, the argument count
//
// @param argv pointer to an array of strings, the arguments to the program,
// one for each argc
///////////////////////////////////////////////////////////////////////////////
// @return int 0x0 if succeeded, !0x0 otherwise
///////////////////////////////////////////////////////////////////////////////
#define UNUSED(X)
///////////////////////////////////////////////////////////////////////////////
int
main(int UNUSED(argc), char** UNUSED(argv))
{
///////////////////////////////////////////////////////////////////////////
std::string terminate = ".";
///////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////
std::string s;
///////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////
unsigned int idx = 0x0;
///////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////
while (true) {
///////////////////////////////////////////////////////////////////////
cout << "Enter a string ('.' to end): " << flush;

///////////////////////////////////////////////////////////////////////
cin >> s;
///////////////////////////////////////////////////////////////////////
if (s != terminate) {
///////////////////////////////////////////////////////////////////
if (FindLongestLargerSubString(s.c_str(), idx)) {
///////////////////////////////////////////////////////////////
cout << "\n\t" << (s.c_str()) + idx << endl << flush;
///////////////////////////////////////////////////////////////
} else {
///////////////////////////////////////////////////////////////
cout << "\n\t"
<< "No P > S found. Broken contract!\n"
<< flush;
///////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////
} else {
///////////////////////////////////////////////////////////////////
break;
///////////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////
return 0x0;
///////////////////////////////////////////////////////////////////////////
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Normalized input string by converting to lowercase:

``````///////////////////////////////////////////////////////////////////////////////
// @file FindLongestLargerSubString.cxx
// @compile g++ -Wall -o FindLongestLargerSubString FindLongestLargerSubString
///////////////////////////////////////////////////////////////////////////////
#include <string.h>
#include <assert.h>
#include <iostream>
#include <algorithm>
///////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////
using namespace std;
///////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////
// @function FindLongestLargerSubString
///////////////////////////////////////////////////////////////////////////////
// @decription Given a string S, print the longest substring P such that P > S
// lexicographically. You may assume that such substring exists.
///////////////////////////////////////////////////////////////////////////////
// @param pS const char* const - the input string [IN]
//
// @param rIdx reference to an unsigned int - upon return this will have the
// the index of the larger substring, unless such a substring does not exist,
// in which case it will be set to UINT_MAX; one consequence of this is
// the length of the input string, excluding the terminating character, must
// be no larger than UINT_MAX - 0x2
///////////////////////////////////////////////////////////////////////////////
// @return bool true if found, false otherwise
///////////////////////////////////////////////////////////////////////////////
// @performance O(n) in number of characters in pS
///////////////////////////////////////////////////////////////////////////////
bool FindLongestLargerSubString(const char* const pS, unsigned int& rIdx)
{
///////////////////////////////////////////////////////////////////////////
assert(pS);
///////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////
bool bRet = false;
///////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////
unsigned int nLen = strlen(pS);
///////////////////////////////////////////////////////////////////////////
// We are assured that such a substring, P, exists. Adopting the convention
// a string is also one of its substrings (akin to every set being its
// own subset), if P exists, then P != S. Why? Well, we are given that
// P > S (lexicographically), and S !> S. To satisfy this, S must be at
// least two characters long. Assert it.
//
// Note: even if caller does not abide by the contract of passing a
// string to us that has at least a lexicographically larger substring,
// we will assert if length of string is less than two characters, but
// also detect that no such substring exist.
///////////////////////////////////////////////////////////////////////////
if (nLen < 0x2) {
///////////////////////////////////////////////////////////////////////
cout << "\n\tBroken contract - input length < 2. Bailing!\n\n"
<< flush;
///////////////////////////////////////////////////////////////////////
assert(nLen > 0x1);
///////////////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////
rIdx = UINT_MAX;
///////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////
// Remember the beginning character.
///////////////////////////////////////////////////////////////////////////
char beginChar = pS[0x0];
///////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////
// We wish to remember the position, if it exists, of a character
// downstream that matches begin.
///////////////////////////////////////////////////////////////////////////
int matchBeginPos = 0x0;
///////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////
// Start from the second character in the string (we are assured that there
// is a second character - see comments above.
///////////////////////////////////////////////////////////////////////////
for (int idx = 0x1; idx < nLen; idx++) {
///////////////////////////////////////////////////////////////////////
if (matchBeginPos == 0x0) {
///////////////////////////////////////////////////////////////////
if (pS[idx] > beginChar) {
///////////////////////////////////////////////////////////////
// We are done
///////////////////////////////////////////////////////////////
rIdx = idx;
///////////////////////////////////////////////////////////////
break;
///////////////////////////////////////////////////////////////
} else if (pS[idx] == beginChar) {
///////////////////////////////////////////////////////////////
matchBeginPos = idx;
///////////////////////////////////////////////////////////////
} else {
///////////////////////////////////////////////////////////////
// Nothing to do.
///////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////
} else {
///////////////////////////////////////////////////////////////////
// Have already seen a character that matches beginChar
///////////////////////////////////////////////////////////////////
if (pS[idx] > pS[idx - matchBeginPos]) {
///////////////////////////////////////////////////////////////
// We are done. Have found it.
///////////////////////////////////////////////////////////////
rIdx = matchBeginPos;
///////////////////////////////////////////////////////////////
break;
///////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////
// If caller hasn't abided by contract of having at least one substring
// P > S lexicographically, then we indicate it with the return value.
///////////////////////////////////////////////////////////////////////////
if (rIdx < UINT_MAX) {
///////////////////////////////////////////////////////////////////////
bRet = true;
///////////////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////
return bRet;
///////////////////////////////////////////////////////////////////////////
}

///////////////////////////////////////////////////////////////////////////////
// @function main
///////////////////////////////////////////////////////////////////////////////
// @decription the entry-point into our program
///////////////////////////////////////////////////////////////////////////////
// @param argc int, the argument count
//
// @param argv pointer to an array of strings, the arguments to the program,
// one for each argc
///////////////////////////////////////////////////////////////////////////////
// @return int 0x0 if succeeded, !0x0 otherwise
///////////////////////////////////////////////////////////////////////////////
#define UNUSED(X)
///////////////////////////////////////////////////////////////////////////////
int
main(int UNUSED(argc), char** UNUSED(argv))
{
///////////////////////////////////////////////////////////////////////////
string terminate = ".";
///////////////////////////////////////////////////////////////////////////
string s;
///////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////
unsigned int idx = 0x0;
///////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////
while (true) {
///////////////////////////////////////////////////////////////////////
cout << "Enter a string ('.' to end): " << flush;
///////////////////////////////////////////////////////////////////////
cin >> s;
///////////////////////////////////////////////////////////////////////
if (s != terminate) {
///////////////////////////////////////////////////////////////////
cout << "\n\tYou entered >" << s << "<\n" << flush;
///////////////////////////////////////////////////////////////////
transform(s.begin(), s.end(), s.begin(), ::tolower);
///////////////////////////////////////////////////////////////////
cout << "\tConverted to lowercase >" << s << "<\n" << flush;
///////////////////////////////////////////////////////////////////
if (FindLongestLargerSubString(s.c_str(), idx)) {
///////////////////////////////////////////////////////////////
cout << "\n\t" << (s.c_str()) + idx << endl << flush;
///////////////////////////////////////////////////////////////
} else {
///////////////////////////////////////////////////////////////
cout << "\n\t"
<< "No P > S found. Broken contract!\n"
<< flush;
///////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////
} else {
///////////////////////////////////////////////////////////////////
break;
///////////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////
return 0x0;
///////////////////////////////////////////////////////////////////////////
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int mystrcmp( char *str1, char *str2)
{
int i = 0;

while(str1[i] == str2[i])
{
if(str1[i] == '/0')
return 0;

i++;
}

return (str1[i] > str2[i] ? 1 : -1);

}

void printsublex(char *str)
{
int i;

for(i = 1; i < strlen(str); i++)
{
if(mystrcmp(&str[i], str) > 0)
{
printf("%s\n", &str[i]);
return;
}
}
return;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int mystrcmp( char *str1, char *str2)
{
int i = 0;

while(str1[i] == str2[i])
{
if(str1[i] == '/0')
return 0;

i++;
}

return (str1[i] > str2[i] ? 1 : -1);

}

void printsublex(char *str)
{
int i;

for(i = 1; i < strlen(str); i++)
{
if(mystrcmp(&str[i], str) > 0)
{
printf("%s\n", &str[i]);
return;
}
}
return;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Java code and test case:

``````public class LongestSubStringInLexicographyOrder
{
private String str;

public LongestSubStringInLexicographyOrder(String str)
{
this.str = str;
}

public void setStr(String str)
{
this.str = str;
}

String findLongestSubString()
{
//Null and length checks
if (this.str == null || this.str.isEmpty())
{
return "";
}
int length = this.str.length();

//Core logic starts
int from=0, to=-1;
int tempFrom=0, tempTo=-1;
for (int i=1; i<length; i++)
{
tempTo=i;
//reset tempFrom whenever you see its not in lexicographic order
if (str.charAt(i) < str.charAt(i-1))
{
tempFrom=i;
}

//keep note of the from and to index if the previous length is smaller
if (to - from < tempTo - tempFrom)
{
from=tempFrom;
to=tempTo;
}

}
return str.substring(from, to+1);
}
}

//Testcase:
import org.junit.Test;

import static org.junit.Assert.*;

public class LongestSubStringInLexicographyOrderTest
{

@Test
public void findLongestSubString() throws Exception
{
LongestSubStringInLexicographyOrder subStringInLexicographyOrder = new LongestSubStringInLexicographyOrder("abcdefghijklmnopqrstuvwxyz");
assertEquals("abcdefghijklmnopqrstuvwxyz", subStringInLexicographyOrder.findLongestSubString());
subStringInLexicographyOrder.setStr("abcdafghijklmnopqrstuvwxyz");
assertEquals("afghijklmnopqrstuvwxyz", subStringInLexicographyOrder.findLongestSubString());
subStringInLexicographyOrder.setStr("abcdafghijklmnopqrstbvwxyz");
assertEquals("afghijklmnopqrst", subStringInLexicographyOrder.findLongestSubString());

subStringInLexicographyOrder.setStr("abcdafghiajklanopqrstbvwxyz");
assertEquals("anopqrst", subStringInLexicographyOrder.findLongestSubString());

subStringInLexicographyOrder.setStr(null);
assertEquals("", subStringInLexicographyOrder.findLongestSubString());

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

A simple function in Java:

``````private static String findSubStr(String str) {

if(str.length() <= 1)
{
return str;
}
int sum1=0, sum2=0;
int start = 1;
for(int i=0, j=start; j<str.length();)
{
if(str.charAt(i) > str.charAt(j))
{
j++;
start = j;
}else{
j++;
i++;
}
}

return str.substring(start);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

private static String findSubStr(String str) {

if(str.length() <= 1)
{
return str;
}
int sum1=0, sum2=0;
int start = 1;
for(int i=0, j=start; j<str.length();)
{
if(str.charAt(i) > str.charAt(j))
{
j++;
start = j;
}else{
j++;
i++;
}
}

return str.substring(start);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//Similar to KMP. Instead of longest suffix that matches a prefix, find the longest suffix
that is lexicographically greater than a prefix.
Time complexity: O(N). Space:O(1).
public String longestSubstring(String str)throws NullPointerException
{
if(str==null)
{
throw new NullPointerException();
}
if(str.length)==0)
{
return "";
}

//Variation of KMP algorithm.Instead of finding longest suffix that matches a prefix. Find the longest suffix that is lexicographically greater then a prefix
int start=-1;
int i=0;
int j=1;
while(j<str.length())
{
//If lexicographically less, move on to the next character
int diff=str.charAt(j)-str.charAt(i);
if(diff>=0)
{
j++;
i++;
if(diff>0)//If current char is lexicographically greater then an earlier character.
{
//j indicates length of this string's prefix, use it to determine start
start=j-i+1;
break;
}
}else
{
j++;
}
}
return start!=-1? str.substring(start):"";
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static String longest(String str) {
for (int i = 1; i< str.length();i++){
String substr = str.substring(i);
if (substr.compareTo(str)>0)
return substr;
}
return "";
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Isn't there a trivial solution? Say S = Px, where P is some arbitrary string and x some arbitrary character. Then P will always lexicographically precede S. So for any string S of length greater than zero, the solution is always the substring of S not containing the last character.

Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
Given a string S, print the longest substring P such that P > S lexicographically.
You may assume that such substring exists.

Solution:
1. Scenario one.
There is a character which greater than the first character and all characters between first character and this character are equal to first character.
xxxxxyabcdefg return "xxxxyabcdefg"
2. Other scenario.
input string: "xxxbxxxaxxxc"
2.1 "....xxxaxxxc vs "xxxbxxxaxxxc"
2.2 "........xxxc" vs "xxxbxxxaxxxc". skip "....xxxa" subtring, and compare from "xxxc"

Time complexity O(n).
*/

``````int compareStr(const char * s1, const char * s2) {
int sz1 = strlen(s1);
int sz2 = strlen(s2);
int i = 0;
while(i < sz2) {
if(s1[i] > s2[i]) return i;
else if(s1[i] < s2[i]) return -i;
i ++;
}
return i;
}

void f(const string & s) {
int sz = s.size();
if(sz <= 1) return ;
int i = 1;
char firstChar = s[i];
bool greaterFound = false;
while(i < sz) {
if(s[i] > firstChar) {
greaterFound = true;
break;
}
else if(s[i] < firstChar) {
break;
}
i ++;
}
if(true == greaterFound) {
printf("%s\n%s\n", s.c_str(), s.c_str() + 1);
return ;
}
i ++;
while(i < sz) {
int pos = compareStr(s.c_str(), s.c_str() + i);
if(pos <= 0) {
printf("%s\n%s\n", s.c_str(), s.c_str() + i);
break;
}
i = i + pos + 1;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def get_bin(a,le):
b=[]
while (a>0):
c=a%2
b.append(c)
a=a/2
b=b[::-1]
while (len(b)<le):
b.insert(0,0)
return b

ret=''
count=0
a='abcde'
for i in range (1,2**len(a)):
g=get_bin(i,len(a))
st=''
for i in range (len(g)):
if g[i]==0:
continue
else:
st=st+str(a[i])
if st>a:
ret=st

print ret``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void printLongestSubstringLexBiggerV2(String str) {

if (str == null || str.length() <= 1) {
return;
}

boolean found = false;
int l = str.length();
int i = 0, j = 1;

while(j < l && !found) {
if (str.charAt(i) < str.charAt(j)) {
found = true;
} else {
j++;
}
}

if (found) {
System.out.println(str.substring(j));
}
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def find_longest_bigger_substring(s):
if len(s) == 0:
return ‘’
i = 1
while i < len(s):
if s[i] > s[0]:
break
i += 1
split_ind = i
if split_ind == len(s)-1:
i = 1
while i < split_ind:
if s[i] == s[0]:
break
i += 1
if s[i:split_ind] <= s[:split_ind-i]:
return s[split_ind:]
else:
return s[i:]
if len(s[:split_ind+1]) > len(s[split_ind:]):
return s[:split_ind+1]
else:
return s[split_ind:]``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def find_longest_bigger_substring(s):
if len(s) == 0:
return ‘’
i = 1
while i < len(s):
if s[i] > s[0]:
break
i += 1
split_ind = i
if split_ind == len(s)-1:
i = 1
while i < split_ind:
if s[i] == s[0]:
break
i += 1
if s[i:split_ind] <= s[:split_ind-i]:
return s[split_ind:]
else:
return s[i:]
if len(s[:split_ind+1]) > len(s[split_ind:]):
return s[:split_ind+1]
else:
return s[split_ind:]``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

why do these comments not work ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package test;

public static void main(String[] args) {

String stringOne = "dztwbcdezfoptjklcd";

lexicography (stringOne);

}

public static void lexicography (String stringOne){

StringBuilder builder =new StringBuilder ();
String maxLexicography = new String();
String auxLexicography = new String();
boolean agregarAux=false;

int iterations=0, iterationsplusOne = 1;

int length = stringOne.length();

while (iterations<length-1 ){

char charStrOne =  stringOne.charAt(iterations);
char charStrTwo =  stringOne.charAt((iterationsplusOne));

if (charStrTwo < charStrOne){

if (auxLexicography.isEmpty()){

agregarAux = true;
maxLexicography = maxLexicography.concat(String.valueOf(charStrOne));

}else{

auxLexicography= auxLexicography.concat(String.valueOf(charStrOne));

if (auxLexicography.length()>maxLexicography.length()){
maxLexicography = new String( auxLexicography);
}
auxLexicography = new String();
}

builder.append(charStrOne);
builder = new StringBuilder ();

}else{

if (agregarAux){
auxLexicography= auxLexicography.concat(String.valueOf(charStrOne));
}else{
maxLexicography = maxLexicography.concat(String.valueOf(charStrOne));
}

builder.append(charStrOne);
}

if (iterationsplusOne == length-1){
builder.append(charStrTwo);

if (auxLexicography.length()>maxLexicography.length()){
maxLexicography = new String( auxLexicography);
}

}

iterations ++;
iterationsplusOne++;

}

System.out.println(maxLexicography);

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static String getLongestSubstringLex (String input ){

if ( (input== null) || (input.length()==1) || (input.equals("")))
return input;

String inputString = input.toLowerCase();
char [] arrChar = inputString.toCharArray();
int firstVal = inputString.charAt(0);
int length = arrChar.length;

for( int i =1; i < length;i++){
int currentVal=inputString.charAt(i);
if(currentVal < firstVal)
return inputString.substring(i,length);

if ( i== (length-1))
return inputString.substring(0,length-2);
}
return input;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Input: xxxxxyabcdefg Output: abcdefg
Input: aaaaXXXbba Output: aaaaxxxb

1) all Input put to lowercase
2) aaaaXXXbb > aaaaXXXbba

Time: O(n) and Space: O(1)

``````public static String getLongestSubstringLex (String input ){

if ( (input== null) || (input.length()==1) || (input.equals("")))
return input;

String inputString = input.toLowerCase();
char [] arrChar = inputString.toCharArray();
int firstVal = inputString.charAt(0);
int length = arrChar.length;

for( int i =1; i < length;i++){
int currentVal=inputString.charAt(i);
if(currentVal < firstVal)
return inputString.substring(i,length);

if ( i== (length-1))
return inputString.substring(0,length-2);

}
return input;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Time complexity - O(n) Space complexity O(n)

``````import org.junit.Assert;
import org.junit.Test;

public class LexicographicalLongestSubstring {
@Test
public void testLexicographicalLongestSubstring() {
Assert.assertEquals("x", getLexicographicalLongestSubstring("bandix"));
Assert.assertEquals("dacdac", getLexicographicalLongestSubstring("bdacdac"));
Assert.assertEquals("ddac", getLexicographicalLongestSubstring("bdacddac"));
Assert.assertEquals("xia", getLexicographicalLongestSubstring("bdacdacxia"));
}

public String getLexicographicalLongestSubstring(String str) {
char[] charArray = str.toCharArray();
int i = 1;
int n = str.length();
int rstart = 0;
while (i < n) {
if (charArray[i] > charArray[rstart]) {
// Reset
rstart = i;
} else if (charArray[i] == charArray[rstart]) {
// compare
int j = i;
int k = rstart;
while (j < n) {
if (charArray[k] < charArray[j]) {
if (charArray[j] > charArray[rstart]) {
// reset
rstart = j;
} else {
rstart = i;
}
i = j + 1;
break;
} else if (charArray[k] > charArray[j]) {
i = j + 1;
break;
}
k++;
j++;
}
}
i++;
}
return str.substring(rstart);
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) time and O(1) space

``````import org.junit.Assert;
import org.junit.Test;

public class LexicographicalLongestSubstring {
@Test
public void testLexicographicalLongestSubstring() {
Assert.assertEquals("x", getLexicographicalLongestSubstring("bandix"));
Assert.assertEquals("dacdac", getLexicographicalLongestSubstring("bdacdac"));
Assert.assertEquals("ddac", getLexicographicalLongestSubstring("bdacddac"));
Assert.assertEquals("xia", getLexicographicalLongestSubstring("bdacdacxia"));
}

public String getLexicographicalLongestSubstring(String str) {
char[] charArray = str.toCharArray();
int i = 1;
int n = str.length();
int rstart = 0;
while (i < n) {
if (charArray[i] > charArray[rstart]) {
// Reset
rstart = i;
} else if (charArray[i] == charArray[rstart]) {
// compare
int j = i;
int k = rstart;
while (j < n) {
if (charArray[k] < charArray[j]) {
if (charArray[j] > charArray[rstart]) {
// reset
rstart = j;
} else {
rstart = i;
}
i = j + 1;
break;
} else if (charArray[k] > charArray[j]) {
i = j + 1;
break;
}
k++;
j++;
}
}
i++;
}
return str.substring(rstart);
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use the Knuth-Morris-Pratt (KMP) algorithm to find the result. It is implicit in the computation of the failure function, no need to apply the pattern to itself.

``````def search_greatest_substr_kmp(pattern):
l = len(pattern)
f = [0] * l
j = 0
i = 1

while i < l:
if pattern[i] > pattern[j]:
# Found a substring that is greater than the prefix itself.
# Take the rest of the string
return pattern[i - j:]
elif pattern[i] == pattern[j]:
# There is match, the suffix matched grows by one
f[i] = f[i - 1] + 1
i += 1
j += 1
elif j > 0:
# Try matching with a smaller feasible suffix
j = f[j - 1]
else:
f[i] = 0
i += 1

return f``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.