Google Interview Question
Software EngineersCountry: United States
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.
/*
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;
}
}
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..
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).
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++;
}
}
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;
}
}
}
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;
}
}
}
}
///////////////////////////////////////////////////////////////////////////////
// @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;
///////////////////////////////////////////////////////////////////////////
}
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;
///////////////////////////////////////////////////////////////////////////
}
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;
}
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;
}
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());
}
}
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);
}
//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):"";
}
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));
}
}
}
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:]
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:]
package test;
public class GoogleLexSubString {
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);
}
}
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;
}
Comments Welcome!!
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;
}
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);
}
}
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);
}
}
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
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).
- EPavlova March 19, 2016