Amazon Interview Question
Country: India
def FindLongestSubString(s1, s2):
if s1 == "" or s2 == "" or s1 == "\0" or s2 == "\0":
return ""
else:
s1 = s1.lower()
s2 = s2.lower()
if s1 == s2:
return s1
else:
if len(s1) < len(s2):
i = len(s1)
while i>0 and not s2.endswith(s1[0:i]):
i -= 1
if i>0:
return s1[0:i]
else:
return ""
else:
i = 0
while i<len(s2) and not s1.startswith(s2[i:]):
i += 1
if i<len(s2):
return s2[i:]
else:
return ""
what about
public class Solution {
public String prefix(String sa, String sb){
int length = -1,temp = -1;
for(int i = sa.length() -1 ;i>=0;i--){
length = -1;temp = -1;
if(sa.charAt(i)==sb.charAt(sb.length()-1)){
temp = compareStrings(sa.substring(0,i), sb.substring(0,sb.length()-1));
if(temp >0){
length = 1 + temp;
break;
}
}
}
if(length > 0)
return sa.substring(0,length);
return "";
}
public int compareStrings(String s1,String s2){
int la = s1.length()-1, lb = s2.length() -1;
if(s1.length()==0) return 0;
if((lb<0)&&(la>=0)) return -1;
if(s1.charAt(la)==s2.charAt(lb)){
la = compareStrings(s1.substring(0,la), s2.substring(0,lb));
if(la < 0 )
return -1;
else
return 1 + la;
}
else
return -1;
}
public static void main(String[] args) {
String s1 = "AAAAB";
String s2 = "AAAAAB";
System.out.println("first string is : "+ s1);
System.out.println("second string is : "+ s2);
Solution obj = new Solution();
String lcs = obj.prefix(s1, s2);
System.out.println("The longest substring is : "+lcs);
}
}
public static String longestPrefixSuffix(String s1, String s2) {
final StringBuilder builder = new StringBuilder();
int s1p = 0;
int s2p = 0;
while (s1p < s1.length() && s2p < s2.length()) {
if (s1.charAt(s1p) == s2.charAt(s2p)) {
builder.append(s1.charAt(s1p));
s1p++;
} else {
s1p = 0;
builder.setLength(0);
}
s2p++;
}
return builder.toString();
}
We can create two pointers, for the first and the second string. Increment second each iteration, first increment if there is the matching, if matching is not present - reset pointer and temporary result.
Nice catch.
It's simple to fix that changing the while loop:
while (s1p < s1.length() && s2p < s2.length()) {
if (s1.charAt(s1p) == s2.charAt(s2p)) {
builder.append(s1.charAt(s1p));
s1p++;
s2p++;
} else {
s1p = 0;
s2p -= s1p + 1;
builder.setLength(0);
}
}
Unfortunately the complexity is growing from nice O(n) to O(n^2) in worst case.
/**
* Java
*/
public class PrefixSuffix {
public PrefixSuffix() {
super();
}
public static String preSuf(String s1, String s2) {
String match = "";
int maxLen = (s2.length() > s1.length()) ? s1.length() : s2.length();
for (int i=1; i<=maxLen; i++) {
if (s1.substring(0,i).equals(s2.substring(s2.length()-i))) {
match = s1.substring(0,i);
}
}
return match;
}
public static void main(String[] args) {
String s1 = "gggbingbinghello";
String s2 = "abcdbingasdfgggbing";
String s3 = PrefixSuffix.preSuf(s1, s2);
System.out.println("Answer is: " + s3);
}
}
no, I don't think so
I have made a solution having worst case O(n^2).
and the answer by Jordi Marés is also O(n^2) in worst case
There is not a solution in o(n) (that's little-O) because you have to look at all the characters of the string you're given.
As far as coding in O(n) (big-O), it's not that easy (though possible). I'd be interested in hearing how you solved it.
@eugene.yarovoi
no that's not in O(n), i have done in O(n^2)
have done similar as Jordi Marés Soler with little more optimization,
--no list
--no sorting of list
--not calculating other indexes after getting my answer
(putting my solution here)
Yes, it can be solved in O(n).
Construct a suffix tree for string s2 in O(n) time using Ukkonen's algorithm for constructing suffix trees - O(n) time and O(n) extra space.
Search string s1 in the suffix tree constructed in above step - O(n) time
The longest matched prefix of string s1 is the required substring.
Total time - O(n) and extra space used is O(n)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
char *findSubstring(const char *str1, const char*str2)
{
int len1 = strlen(str1);
int len2 = strlen(str2);
// find maximum length of common substring
int n = 1;
int max = 0;
while (n <= len1 && n <= len2) {
if (!strncmp(str1, str2 + len2 - n, n)) max = n;
n++;
}
// create substring
char *output = (char*)malloc(max+1);
strncpy(output, str1, max);
output[max] = '\0';
return output;
}
int main()
{
const char *str1 = "ABCABCzzzzzzzzzzzzzzzzzzzzzzzzzzz";
const char *str2 = "xxxxxxxxxxxxxxxABCABC";
char *output = findSubstring(str1, str2);
printf("[%s]\n", output);
free(output);
return 0;
}
i think this algo will work :
1.scan s1 from back and stop when u find matching character to last character of s2.
2.start back scan of s1 and s2 frm there till both match
3.if now we reach -1 for s1 then we find prefix as continue from there with above steps
int i=s1.length()-1,j;
while(i!=-1)
{ for(;i>=0;i--)
if(s1[i]==s2[s2.length()-1])
break;
j=s2.length()-1;
while(i>=0 && s1[i]==s2[j])
{
i--;
j--;
}
}
Tested and appears to work 100%. Added features of skipping ahead (if length stringB<stringA) & checking first and last character before checking entire string. A few more things can be done for efficiency (i.e. if len == 0 or len == 1) and error checking, but not without cheating too much and spending several hours to write the most perfect elegant solution ever.
//test the code
public static void main(String[] args) {
String stringA = "ABABCDEFGxxxxxxxxxxx";
String stringB = "xxxABABCDEFG";
String match = prefixSuffix(stringA, stringB);
System.out.println("Match: "+match);
}
public static String prefixSuffix(String stringA, String stringB){
int lenA = stringA.length();
int lenB = stringB.length();
if (lenA == 0 || lenB == 0) return "";
int startPos = (lenA < lenB) ? lenB-lenA: 0;//can skip ahead for efficiency.
for (int i = startPos; i < lenB; i++) {
if (compareStrings(stringA, stringB, 0, i, lenB-i-1)){
return stringA.substring(0, lenB-i);
}
}
return "";
}
//helper for prefix suffix comparator.
public static boolean compareStrings (String stringA, String stringB,int indexA, int indexB, int length) {
//TODO throw exception if index+length out of range
if (stringA.charAt(indexA) != stringB.charAt(indexB)) {return false;}//check first
if (stringA.charAt(indexA+length) != stringB.charAt(indexB+length)) {return false;}//check last
for (int j = 1; j < length-1; j++) {//check middle
if (stringA.charAt(indexA+j) != stringB.charAt(indexB+j)) {return false;}//check first
}
return true;
}
Tested and appears to work 100%. Added features of skipping ahead (if length stringB<stringA) & checking first and last character before checking entire string. A few more things can be done for efficiency (i.e. if len == 0 or len == 1) and error checking, but not without cheating too much and spending several hours to write the most perfect elegant solution ever.
//test the code
public static void main(String[] args) {
String stringA = "ABABCDEFGxxxxxxxxxxx";
String stringB = "xxxABABCDEFG";
String match = prefixSuffix(stringA, stringB);
System.out.println("Match: "+match);
}
public static String prefixSuffix(String stringA, String stringB){
int lenA = stringA.length();
int lenB = stringB.length();
if (lenA == 0 || lenB == 0) return "";
int startPos = (lenA < lenB) ? lenB-lenA: 0;//can skip ahead for efficiency.
for (int i = startPos; i < lenB; i++) {
if (compareStrings(stringA, stringB, 0, i, lenB-i-1)){
return stringA.substring(0, lenB-i);
}
}
return "";
}
//helper for prefix suffix comparator.
public static boolean compareStrings (String stringA, String stringB,int indexA, int indexB, int length) {
//TODO throw exception if index+length out of range
if (stringA.charAt(indexA) != stringB.charAt(indexB)) {return false;}//check first
if (stringA.charAt(indexA+length) != stringB.charAt(indexB+length)) {return false;}//check last
for (int j = 1; j < length-1; j++) {//check middle
if (stringA.charAt(indexA+j) != stringB.charAt(indexB+j)) {return false;}//check first
}
return true;
}
Maybe not the fastest solution, but...
static String longestCommonPrefixAndSuffix(String s1, String s2) {
String solution = s1.substring(0, Math.min(s1.length(), s2.length()));
while (solution.length() > 0) {
if (s2.endsWith(solution)) {
return solution;
}
solution = solution.substring(0, solution.length() - 1);
}
return solution;
}
public static String PrefixSuffix(String stringA, String stringB)
{
for (int i = stringA.Length; i > 0; i--)
{
string longestMatchingSubstring = stringA.Substring(0, i);
int suffixStartPosition = stringB.LastIndexOf(longestMatchingSubstring);
if ((suffixStartPosition != -1) && (suffixStartPosition + i == stringB.Length))
return longestMatchingSubstring;
}
return "No Match Exists";
}
Given s1 and s2, where we are interested in finding the longest prefix of s1 that matches a suffix of s2, we can do the following:
1- Build a suffix tree on all the suffixes of s2: i.e. s2[i..n] for i=0..n-1 and n is size of s2. This takes O(n)
2- Traverse the suffix tree using s1: if at some point we reach a leaf, we have found the solution. If the traversal ends at a non-leaf node, there is no such suffix.
void LongestPrefixSufixMatch(char *s1, char *s2)
{
if(!*s1 || !*s2)
return;
int n1=strlen(s1);
int n2=strlen(s2);
int l=n1<=n2?n1:n2;
int len,i,I,k,end=-1;
int max=INT_MIN;
for(i=0;i<l;i++)
{
if(s1[i]==s2[n2-1])
{
I=i;
k=0;
len=0;
while(I>=0 && s1[I]==s2[n2-1-k])
{
I--;
k++;
len++;
}
if(len>max)
{
max=len;
end=i;
}
}
}
for(i=0;i<=end;i++)
printf("%c",s1[i]);
printf("\n");
}
#include<stdio.h>
char * long_sub_str( char *str1 , char *str2 )
{
int str1_len = strlen(str1);
int str2_len = strlen(str2);
char *stPtr = str1, *enPtr = str2+str2_len ;
int len = (str1_len > str2_len) ? str1_len : str2_len ;
int done = 0, str_len = 1;
while( str_len < len )
{
done = strncmp(str1, enPtr-str_len, str_len) ? done : str_len;
str_len++;
}
return enPtr-done;
}
int main()
{
char *str1 = "ABCDee";
char *str2 = "xxxxxxxxxxxxxxxxxxxxABC";
char *lstr = long_sub_str(str1,str2);
printf("%s", lstr);
}
#include<stdio.h>
char * long_sub_str( char *str1 , char *str2 )
{
int str1_len = strlen(str1);
int str2_len = strlen(str2);
char *stPtr = str1, *enPtr = str2+str2_len ;
int len = (str1_len > str2_len) ? str1_len : str2_len ;
int done = 0, str_len = 1;
while( str_len < len )
{
done = strncmp(str1, enPtr-str_len, str_len) ? done : str_len;
str_len++;
}
return enPtr-done;
}
int main()
{
char *str1 = "ABCDee";
char *str2 = "xxxxxxxxxxxxxxxxxxxxABC";
char *lstr = long_sub_str(str1,str2);
printf("%s", lstr);
}
static string LongestPrefixAndSuffix(string s1, string s2)
{
if (String.IsNullOrEmpty(s1) || String.IsNullOrEmpty(s2))
return String.Empty;
for (int i = 0; i < s2.Length; i++)
{
// search for a potential 'start' character in the
// suffix string
if (s2[i] == s1[0] &&
String.Compare(s1,0,s2,i, s2.Length - i) == 0)
{
return s2.Substring(i);
}
}
return String.Empty;
}
This is first step in KMP algorithm. Same as building the KMP table. Following is o(n) time complexity algo where n is number of characters in second string.
public static String longestPrefix ( String first, String second ) {
if ( first == null || second == null || first.isEmpty() || second.isEmpty() ) return "";
if ( first.equals(second)) return first;
char[] firstChars = first.toCharArray();
char[] secondChars = second.toCharArray();
int matched = 0;
for ( int j=1; j<secondChars.length;) {
if ( firstChars[matched] == secondChars[j]) {
matched++;
j++;
} else {
if ( matched > 0 ) {
matched=0;
} else {
j++;
}
}
}
if ( matched > 0 ) return second.substring(second.length()-matched, second.length());
else return "";
}
public class PrefixSuffix {
public static void main(String[] args) {
String A = "ABCDEF";
String B = "ABCABC";
System.out.println(prefixSuffix(A,B));
}
public static String prefixSuffix(String A, String B)
{
int x = 0; // index for A
int marker = -1; // index where the suffix starts on B
for(int y=0; y<B.length(); y++)
{
char atA = A.charAt(x);
char atB = B.charAt(y);
if(atA == atB)
{
if(x == 0) marker = y;
x++;
}
else
{
x = 0;
if(marker != -1) y--; // For a new sequence to match move back one index
marker = -1;
}
}
if(marker >=0 ) return B.substring(marker);
else return null;
}
}
public class PrefixSuffix {
public static void main(String[] args) {
String A = "ABCDEF";
String B = "ABCABC";
System.out.println(prefixSuffix(A,B));
}
public static String prefixSuffix(String A, String B)
{
int x = 0; // index for A
int marker = -1; // index where the suffix starts on B
for(int y=0; y<B.length(); y++)
{
char atA = A.charAt(x);
char atB = B.charAt(y);
if(atA == atB)
{
if(x == 0) marker = y;
x++;
}
else
{
x = 0;
if(marker != -1) y--; // For a new sequence to match move back one index
marker = -1;
}
}
if(marker >=0 ) return B.substring(marker);
else return null;
}
}
string preSuf(string s1, string s2){
if (s1.size() == 0 | s2.size() == 0)
return "string size must be greater than 0";
int p_length = (int)min(s1.size(),s2.size());
for (int i = p_length; i > 0; i--){
if(s1.substr(0,i) == s2.substr(s2.size()-i,i))
return s1.substr(0,i);
continue;
}
return "common prefix/suffix not found";
}
string preSuf(string s1, string s2){
if (s1.size() == 0 | s2.size() == 0)
return "string size must be greater than 0";
int p_length = (int)min(s1.size(),s2.size());
for (int i = p_length; i > 0; i--){
if(s1.substr(0,i) == s2.substr(s2.size()-i,i))
return s1.substr(0,i);
continue;
}
return "common prefix/suffix not found";
}
Algorithm:
1. Search the first char of S1 in S2 (from last). If S1 prefix has consecutive duplicates (AAAB) then move backwards (from the position we just found) in S2 until we different char.
2. Now, compare S1 from beginning and in S2 from the point we got in step 1.
3. Compare till we found mismatch or end of the string(s). If we are end of S2 then the traversed string is longest sub string.
Example:
S1 = "abcdef" and S2 = "xyxabc"
1. after first step the s2 pointer points to s[3] i.e a
2. Now start compare from s1[0] and s2[3]
Since our search ends at end of S2 the longest sub string is 'abc'
Let me know, If I am missing any cases.
private static String find(String f, String s) {
char first = f.charAt(0);
int index = s.lastIndexOf((int) first);
int ind = 1;
boolean b = true;
if (index >= 0) {
for (int i = index + 1; i < s.length(); i++) {
if (f.charAt(ind) == s.charAt(i)) {
ind++;
} else {
b = false;
break;
}
}
}
return b ? s.substring(index) : "";
}
/**
* to find the commonRegion which is prifix of read1 as well as suffix of read2
*
* @param read1
* @param read2
* @return String (the commonRegion)
*/
public String getCommonRegion(String read1, String read2){
List<Integer> occurences = new ArrayList<Integer>();
int maxCommonLength = read1.length()>read2.length()? read2.length() : read1.length();
int l1 = read1.length();
int l2 = read2.length();
for(int i=0;i<maxCommonLength;i++){
if(read1.charAt(0) == read2.charAt(l2-maxCommonLength+i)
&& (read1.charAt(maxCommonLength-i-1)==read2.charAt(l2-1))){
int k = l2-maxCommonLength+i;
boolean isCommomRegion = true;
for(int j=1;k+j<l2;j++)
if(read1.charAt(j)!=read2.charAt(k+j)){
isCommomRegion = false;
break;
}
if(isCommomRegion)
return read2.substring(k);
}
}
return "";
}
What about:
public String prefixSufix(String s1, String s2) {
if (s1.isEmpty() || s2.isEmpty()) return "";
char lastPrefixChar = s2.charAt(s2.length() - 1);
String biggerSubstring = "";
boolean found = false;
while (!found) {
int lastIndex = s1.lastIndexOf(lastPrefixChar);
String endingSubstring = s1.substring(0, lastIndex + 1);
if (s2.endsWith(endingSubstring)) {
found = true;
biggerSubstring = endingSubstring;
} else {
s1 = s1.substring(0, lastIndex);
}
}
return biggerSubstring;
}
- Jordi Marés Soler October 15, 2013