Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
@zahidbuet106
Can you please explain step 3 in more detail?
How can the suffixes alone suffice? What do you do when you pass over them?
1) For constant sized alphabet we can build suffix trees using Ukkonen's Algorithm in O(n).
2) For given string S, build a generalized suffix tree of S#S` where S' is reverse of string S and # is delimiting character.
3) Now in this suffix tree, for every suffix i in S, look for lowest common ancestor of (2n-i+1) suffix is S`.
4) count for all such suffixes in the tree to get total count of all palindromes.
5) You can even go further and get longest palindrome. Look for LCA which is deepest in the tree i.e. one whose distance from root is max.
I hope this helps. I am updating the main post.
Special Note: Use Manacher's algorithm to find all the palindromic substring or the longest palindromic substring very simply in O(n) time!
public class ManacherLongestPalindromicSubstring{
public static String void preprocess(String in){
StringBuffer sb = new StringBuffer();
sb.append’#’);
for(int i=0; i<in.length(); i++){
sb.append(in.charAt(i));
sb.append(‘#’);
}
return sb.toString();
}
public static String LongestPalindrome(String in){
/*Preprocess the string to insert special character ‘#’ in the spaced between characters in input and the two outside edges. This is done merely to make the computation identical for both odd and even length input string. */
String S = preprocess(in);
int C = 0; //contains center of current palindrome
int R = 0; //contains the right edge of current palindrome
int[] P = new int[S.length()];
// P[i] contains the length of longest palindrome (in S not original in) centered at i
for(int i=0;i<P.length(); i++)
P[i] = 0;
// for each position find longest palindrome centered at the position, save length in P
for(int i=0; i<S.length; i++){
int i_mirror = 2*C-i; // as C - i_mirror = i - C due to symmetric property
/*When R-i > P[i_mirror] then palindrome at center i_prime contained completely within palindrome centered at C. Else R-i <= P[i_mirror] means that the palindrome at ceter i_mirror doesn’t fully contained in the palindrome centered at C. Then palindrome at i is extendable past R*/
P[i] = (R>i) ? min(P[i_mirror], R-i) : 0;
// if palindrome centered at i is extendable past R then extend R to the right edge of newly extended palindrome
while(S[i+P[i]+1] == S[i-P[i]-1])
P[i]++;
// If palindrome centered at i extend past R then update Center to i
if(i+P[i] > R){
C = i;
R = i+P[i];
}
}
return extractLongest(in, P);
}
public int extractLongest(String in, int[] P){
int longestCenter = 0;
int longestLength = 0;
for(int i=0; i<P.length; i++){
if(P[i] > longestLength){
longestLongest = P[i];
longestCenter = i;
}
}
return in.substring((longestCenter-longestLength-1)/2, longestLemgth);
}
public Set<String> allPalindromicSubstring(String in, int[] P){
HashSet<String> all = new HashSet<String>();
for(int i=0; i<P.length; i++)
if(P[i] != 0)
all.add(in.substring((i-P[i]-1)/2, P[i]));
return all;
}
}
without help of suffix array or a trie, i can think of a solution with O(n*n),where n is string len.
1) for palindromic str len %2 == 1, we can iterate through each index i of str, and check how many substring is palindromic if str[i] is the centre of the substr. the check process is as follow: if str[i-1]==str[i+1],then str[i-1,i,i+1] is a palindromic substr, we can continue to check if str[i-2]==str[i+2], if it is not, quit this iterator.
2) for palindromic str len%2 == 0, the process is similar except that str[i-1]=str[i],then check how many substr is palindromic.
import java.util.HashSet;
import java.util.Set;
public class UniqueSubstringsInAStringThatArePalindromes {
public static void main(
String[] args) {
String str = args[0];
Set<String> set = new HashSet<String>();
for (int i = 0; i < str.length(); i++)
for (int j = i+1; j <= str.length(); j++)
if (isPalindrome(str.substring(i, j)))
set.add(str.substring(i, j));
System.out.println(set);
}
public static boolean isPalindrome(
String str) {
if (str.length() > 0) {
for (int i = 0, j = str.length() - 1; i <= j; i++, j--) {
if (str.charAt(i) == str.charAt(j))
continue;
else
return false;
}
return true;
} else
return false;
}
}
Here is reasonable approach without suffix array and trie though.
stevekrenzel.com/articles/longest-palnidrome
You have to modify algorithm slightly to count all intermediate palindromes.
This code can generate only the longest contiguous substring..But I think that is not what is required.
you can do this using suffix Tree and Suffix arrays. O(nlgn) solution
1. For constant sized alphabet we can build suffix trees using Ukkonen's Algorithm in O(n).
2. Traverse the tree lexicographically and populate the suffix array.
3. Pass over suffix array once to get total number of palindromic substrings in the input string.
More Specifically:
- zahidbuet106 December 16, 2013