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;
	    }

- EPavlova March 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Neat! Like it.

- Alex M. May 19, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Terio November 30, 2016 | Flag
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..

- krbchd March 17, 2016 | Flag Reply
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).

- EPavlova March 17, 2016 | Flag Reply
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++;
	}
}

- Abrham Kahsay March 17, 2016 | Flag Reply
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;
                }
            }
           
        }
    }

- Anonymous March 17, 2016 | Flag Reply
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;
		}
	}
}

- kyduke March 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
      }
    }
  }
}

- pacaro April 09, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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).

- Alex M. May 19, 2016 | Flag
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:]

- ChrisZhang1224 March 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- kyduke March 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- deepshikhaagrl March 17, 2016 | Flag Reply
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.

- kyduke March 17, 2016 | Flag
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;
    ///////////////////////////////////////////////////////////////////////////
}

- sm March 18, 2016 | Flag Reply
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;
    ///////////////////////////////////////////////////////////////////////////
}

- sm March 19, 2016 | Flag Reply
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;
}

- Anonymous March 19, 2016 | Flag Reply
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;
}

- Anonymous March 19, 2016 | Flag Reply
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());


    }
}

- SHR March 25, 2016 | Flag Reply
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);
	}

- Zesta March 26, 2016 | Flag Reply
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);
}

- zesta March 26, 2016 | Flag Reply
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):"";
}

- divm01986 April 05, 2016 | Flag Reply
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 "";
	}

- javista April 09, 2016 | Flag Reply
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.

- Morbock April 12, 2016 | Flag Reply
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;
    }
}

- zombie April 18, 2016 | Flag Reply
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

- Soumil Kulkarni April 28, 2016 | Flag Reply
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));
		}
	}
	
}

- guilhebl May 04, 2016 | Flag Reply
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:]

- Anonymous May 18, 2016 | Flag Reply
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:]

- Anonymous May 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

why do these comments not work ?

- Scott May 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
		
	}

}

- israAzul June 04, 2016 | Flag Reply
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;
	}

- koeber99 June 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- koeber99 June 12, 2016 | Flag Reply
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);
    }

}

- darklight July 06, 2016 | Flag Reply
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);
    }

}

- darklight July 06, 2016 | Flag Reply
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

- Terio November 30, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More