Adobe Interview Question Software Engineer / Developers
Country: India
Interview Type: Phone Interview
The question asks for distinct palindromes. I believe Manacher's algorithm won't work in this case.
I also think the best answer involves suffix trees, but I'm not sure how to construct the tree to check the distinct palindromes
Here is source code ..
package org.ajeet.algorithms.dp;
public class Manacher {
private int[] p; // p[i] = length of longest palindromic substring of t, centered at i
private String s; // original string
private char[] t; // transformed string
public Manacher(String s) {
this.s = s;
t = preprocess(s);
p = new int[t.length];
int center = 0, right = 0;
for (int i = 1; i < t.length-1; i++) {
int mirror = 2*center - i;
if (right > i) p[i] = Math.min(right - i, p[mirror]);
// attempt to expand palindrome centered at i
while (t[i + (1 + p[i])] == t[i - (1 + p[i])])
p[i]++;
// if palindrome centered at i expands past right,
// adjust center based on expanded palindrome.
if (i + p[i] > right) {
center = i;
right = i + p[i];
}
}
}
// Transform s into t.
// For example, if s = "abba", then t = "$#a#b#b#a#@"
// the # are interleaved to avoid even/odd-length palindromes uniformly
// $ and @ are prepended and appended to each end to avoid bounds checking
public char[] preprocess(String s) {
char[] t = new char[s.length()*2 + 3];
t[0] = '$';
t[s.length()*2 + 2] = '@';
for (int i = 0; i < s.length(); i++) {
t[2*i + 1] = '#';
t[2*i + 2] = s.charAt(i);
}
t[s.length()*2 + 1] = '#';
return t;
}
// longest palindromic substring
public String longestPalindromicSubstring() {
int length = 0; // length of longest palindromic substring
int center = 0; // center of longest palindromic substring
for (int i = 1; i < p.length-1; i++) {
if (p[i] > length) {
length = p[i];
center = i;
}
}
return s.substring((center - 1 - length) / 2, (center - 1 + length) / 2);
}
// longest palindromic substring centered at index i/2
public String longestPalindromicSubstring(int i) {
i = i + 2;
int length = p[i];
int center = i;
return s.substring((center - 1 - length) / 2, (center - 1 + length) / 2);
}
// test client
public static void main(String[] args) {
String s = "aba";
Manacher manacher = new Manacher(s);
//Here is longest
System.out.println(manacher.longestPalindromicSubstring());
//All palindromes
for (int i = 0; i < 2*s.length(); i++)
System.out.println(i + ": " + manacher.longestPalindromicSubstring(i));
}
}
Sorry i missed the method (it utilize Manacher algo to count all distinct palindromes)..
public Map<String, Boolean> getAllPalindromicSubstring(String source){
Map<String, Boolean> result = new HashMap<String, Boolean>();
for (int i = 0; i < 2*s.length(); i++){
String tmp = this.longestPalindromicSubstring(i);
if(tmp != null && !tmp.equals("") && !result.containsKey(tmp)){
result.put(tmp, true);
}
}
//Manacher algorithm skips a single character if it occures in a bigger palindrome. So need to re iterate once more to add missing single character palindromes.
for (int i = 0; i < source.length(); i++){
String tmp = source.charAt(i)+"";
if(!result.containsKey(tmp)){
result.put(tmp, true);
}
}
return result;
}
String s = "aba";
Manacher manacher = new Manacher(s);
//Here is longest
System.out.println(manacher.longestPalindromicSubstring());
//All palindromes
Map<String, Boolean> palindromes = manacher.getAllPalindromicSubstring(s);
Manacher's algortihm gives all the possible palindromic substrings. To get the distinct substrings, we can use a hash table and reject the duplicated ones or build a trie.
Could u plz provide me code to implement Manacher algorithm to count distinct palindromes. I need it
Modify manacher to use hashing -> become N^2 instead of N for regular Manacher
Now modify hashing to use a rabin karp type optimization -> becomes N again
#include<iostream>
#include<string>
using namespace std;
bool isPalindrome(string,int,int);
int palindrome_count(string str){
int count = 0;
for(int i=0; i < str.size(); i++){
for(int j=i ; j< str.size(); j++){
if(isPalindrome(str,i,j))
count++;
}
}
return count;
}
bool isPalindrome(string str,int start,int end){
while(start<=end){
if(str[start] != str[end])
return false;
else if(str[start] == str[end]){
start++;
end--;
}
}
return true;
}
int main(){
string str = "abcdcba";
int count;
count = palindrome_count(str);
cout<<"\n"<<count;
}
lets say string given is T.
1. build a sufix tree of T$.
ex- T = aba.
then suffix = {a$, ba$, aba$}.
2. find reverse of given string T".
then ad suffix of T'' in the earlier suffix tree.
sufix of T" = {a#, ba#, aba#}
3. traverse the suffix tree. -> find the path which have ended with # and $.
these will be the pallindrome of the string.
This question is from an ongoing competition on CodeChef.
- Miguel Oliveira December 13, 2013Don't use this site to cheat.