Microsoft Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
public static int pal(String s) {
char[] array = s.toCharArray();
int maxCounter = 1;
for (int i = 1; i < array.length - 1; i++) {
int counter = 1;
int l = i - 1;
int r = i + 1;
while ( l > 0 && r < array.length - 1 ) {
if (array[l] == array[r]) {
counter++;
r++;
l--;
} else {
break;
}
}
if (counter > maxCounter) {
maxCounter = counter;
}
}
return maxCounter;
}
Not entirely sure this is O(n) time. It is def O(1) space.
It is called Manacher algorithm. For excellent explanation of Manacher algorithm see,
leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
It is surely not O(N). You are checking for palindrome for every possible position. Checking palindrome takes O(N) time and there are O(N) such positions. So, it is O(N^2) algorithm.
this is the first solution i gave, but you need to give O(n) + O(1) complexity solution, I finally gave the solution of required bound
I fixed a few bugs in panos' answer. It wasn't handling cases such as "madamyracecarxzyjj" correctly. Also, pal() was returning a counter instead of the number of characters in the palindrome. Finally, I adapted it to C++.
int pal(string s)
{
int maxCounter = 1;
for (int i = 1; i < s.length() - 1; i++) {
int counter = 1;
int l = i - 1;
int r = i + 1;
while ( l >= 0 && r <= s.length() - 1 )
{
//cout << "s[l] :" << s[l] << " s[r]: " << s[r] << endl;
if (s[l] == s[r]) {
counter++;
//cout << "counter: " << counter << endl;
r++;
l--;
}
else
{
if (counter > maxCounter)
{
maxCounter = ((counter * 2) - 1);
}
break;
}
}
}
return maxCounter;
}
you sure it can be done in O(n)? basically you don't know the start point and end point of the palindrome, so I think you need at least O(n^2). Let me know if I was wrong.
You can use this recursion formulae
P(crawlerFromBeginning,crawlerFromEnd) =
if(word[crawlerFromBeginning]== word[crawlerFromEnd]){
2 + P(crawlerFromBeginning+1,crawlerFromEnd-1) // if the characters at the position
are equal
}
else{
max(P(crawlerFromBeginning+1,crawlerFromEnd) ,P(crawlerFromBeginning,crawlerFromEnd-1) )
}
I realize above algo doesn't taking care of Even cases (like: cdeedc, aaaa ) & what about string length 2 (aa) .
So i am fixing the code now.
public int pal(String s) {
// null pointer check for s and length of s if 0
if (s == null)
return 0;
int len = s.length();
if (len < 2) {
return len;
}
char[] array = s.toCharArray();
// the algorithm will fail for strings of length 2
if (len == 2) {
if (array[0] == array[1])
return len;
else
return 0;
}
int maxCount = 1;
for (int center = 1; center < len - 1; center++) {
int palinLen = 1;
int l = center - 1;
int r = center + 1;
// Even Case handled here
// in case of aaa center + 2 (where center=1) = 3 < 3 means this case will not land in
// Even case;
if (array[center] == array[center + 1] && (center + 2 < len)) {
r = center + 2;
palinLen++;
}
while (l >= 0 && r <= len - 1) {
if (array[l] == array[r]) {
r++;
l--;
palinLen += 2;
}
}
if (l < 0 || r == len) {
if (palinLen > maxCount) {
maxCount = palinLen;
}
}
}
return maxCount;
}
There are a few fixes the above code required:-
1. the while loop while (l >= 0 && r <= len - 1) required to check for l<=r as well.
2. Inside this loop if if (array[l] != array[r]) we had to break out of this loop.
3. The last if clause if (l < 0 || r == len) is not required.
public static void main(String args[]) {
String str = "ABCDMNPPNMDCBAOPOABCDMPNSSNPM";
System.out.println(pal(str));
}
static public int pal(String s) {
// null pointer check for s and length of s if 0
if (s == null)
return 0;
int len = s.length();
if (len < 2) {
return len;
}
char[] array = s.toCharArray();
// the algorithm will fail for strings of length 2
if (len == 2) {
if (array[0] == array[1])
return len;
else
return 0;
}
int maxCount = 1;
for (int center = 1; center < len - 1; center++) {
int palinLen = 1;
int l = center - 1;
int r = center + 1;
// Even Case handled here
// in case of aaa center + 2 (where center=1) = 3 < 3 means this
// case will not land in
// Even case;
if (array[center] == array[center + 1] && (center + 2 < len)) {
r = center + 2;
palinLen++;
}
while (l >= 0 && r <= len - 1 && l<=r) {
if (array[l] == array[r]) {
r++;
l--;
palinLen += 2;
}
else
{
break;
}
}
if (palinLen > maxCount) {
maxCount = palinLen;
}
}
return maxCount;
}
I fixed panos's code a little bit. But it's still not O(n). C# code.
static int ReturnMaxPalindromeLength(string value)
{
if (string.IsNullOrEmpty(value) || value.Length < 2)
return 0;
int currentlength = 0;
int maxLength = 0;
for (int i = 0; i < value.Length; i++)
{
int left = i - 1;
int right = i + 1;
if (left < 0 || right > value.Length - 1 || !value[left].Equals(value[right]))
continue;
while(left >= 0 && right <= value.Length - 1)
{
if (value[left].Equals(value[right]))
{
currentlength++;
left--;
right++;
}
else
{
break;
}
}
if (currentlength > maxLength)
maxLength = currentlength;
currentlength = 0;
}
return maxLength*2 + 1;
}
string longest_around(const string& str, int i, int j)
{
string longest;
int left = i, right = j;
while(str[left] == str[right])
{
longest = str[left] + longest + str[right];
++left; ++right;
}
return longest;
}
string longest_palindrome(const string& str)
{
string result;
for(int i = 0; i < str.length() - 1; ++i)
{
string pal = longest_around(str, i, i);
if(pal.length() > result.length())
{
result = pal;
}
pal = longest_around(str, i, i + 1);
if(pal.length() > result.length())
{
result = pal;
}
}
return result;
}
public class LongestPalindrome {
public static void main(String[] args){
System.out.println("Enter the string");
String str1=new String();
//String str1=new String();
Scanner s=new Scanner(System.in);
str1=s.nextLine();
char[] s1 = str1.toCharArray();
char [] s2 = new char[2*str1.length()+1];
int l,r,count,maxcount=1;
for(int j=0;j<2*str1.length()+1;j++)
{
if(j%2==0) {
s2[j]='#' ;
}
else{
s2[j] = s1[j/2];
}
}
/* for(int k=0;k<2*str1.length()+1;k++)
System.out.print(s2[k]); */
for(int i=1;i<2*str1.length()+1;i++){
count=0;
l=i-1;
r=i+1;
while(l>=0 && r<=2*str1.length() && s2[l]==s2[r])
{
count++;
l--;
r++;
}
if(count>maxcount){
maxcount=count;
}
}
System.out.println("");
System.out.println("the maximum sized palindrome is " + maxcount);
}
}
In order to find the Longest Palindromic Substring in O(n) we need to apply the Manacher's Algorithm. It works like this:
Let's say that we have the input string S:
S = ccacaacaba
First Step: Preprocess input string by inserting special Character '#' between each char in the string:
T = ^#c#c#a#c#a#a#c#a#b#a#$
Characters ^ and $ are used just to avoid bounds checking. Let's call this preprocessed String T.
Then we need to create an Array (P) with the same size of the preprocessed String T. This array will have at each position i the size of the longest Palindrome centered in i.
T = ^ # c # c # a # c # a # a # c # a # b # a # $
P = 0 0 1 2 1 0 3 0 3 0 1 6 1 0 3 0 1 0 3 0 1 0
In order to compute all the value of P efficiently, we can use the simmetric property of P, for example if we take into account the palindrome centered at position i=11, T[11] ("acaaca"), we can see that the value of P at position i+1 is equal at the value of P at position i-1 (T[i-1]==T[i+1]) and T[i-2]==T[i+2], T[i-3]==T[i+3] ... T[i]==T[i_mirror].
The problem is that this property is not always valid. Let's take into account i+5 and i-5. Note T[i+5]==1 and T[i-5]==3. This happens because the Palindrome centered at i-5 expands beyond the left limit of the simmetric center that we took into account P[11], with palindromic length of 6. This means that the simmetric property is guaranteed only if P[i_mirror] <= R-i, where R is the Right limit of the Palindrome centered at the simmetric center C that we are taking into account (in this case P[11]). If R-i<P[i_mirror] then we only know that P[i]>=R-i. Thus we need to expand the palindrome size centered at i char by char:
while(T.charAt(i+1+P[i])==T.charAt(i-1-P[i]))
P[i]++;
the last step is to know when to move the simmetric center C and the right limit R to the right with i. This happens when i past the right limit R of C:
if(R<i+P[i]) {
C=i;
R=i+P[i];
}
Expanding a palindrome take at most O(n) and moving the center also at most O(n), therefore this algorithm performs with O(2n) complexity, thus this is a linear algorithm to find the longest Palindrome substring.
In my code you can use
String stringGenerator(int n)
to generate a random String from the alphabet (first var in the method) of length n;
the method
String manacherizeString(String s)
preprocess the input string by inserting special characters and the longest palindromic substring is retrieved by the method
String manacher(String s)
Here is the complete code implementing the Manacher Algorithm in java:
import java.util.Random;
public class LongestPalindromicSubstring {
public static String manacherizeString(String s) {
if(s.length()==0) return "^$";
String p = "^#";
for(int i=0;i<s.length();i++) {
p+=s.charAt(i)+"#";
}
p+="$";
return p;
}
public static String manacher(String s) {
String T = manacherizeString(s);
System.out.println(T);
int R = 0;
int C = 0;
int imirror;
int[] P = new int[T.length()];
for(int i=1;i<T.length()-1;i++) {
imirror = C-(i-C);
if(R>i) {
P[i] = Math.min(P[imirror],R-i);
}
else {
P[i] = 0;
}
while(T.charAt(i+1+P[i])==T.charAt(i-1-P[i]))
P[i]++;
if(R<i+P[i]) {
C=i;
R=i+P[i];
}
}
int maxLength = 0;
int maxCenter = 0;
for(int i=0;i<P.length-1;i++) {
System.out.print(P[i]+" ");
if(P[i]>maxLength) {
maxLength = P[i];
maxCenter = i;
}
}
System.out.println("\nMaxLength: "+maxLength+" MaxCenter: "+maxCenter);
return s.substring((maxCenter-1-maxLength)/2,((maxCenter-1-maxLength)/2)+maxLength);
}
public static String stringGenerator(int n) {
//String alphabet = "abcdefghiklmnopqrstuvxyz";
String alphabet = "abc";
String s = "";
Random r = new Random();
for(int i=0;i<n;i++) {
s+=alphabet.charAt(r.nextInt(alphabet.length()));
}
return s;
}
public static void main(String[] args) {
String s = stringGenerator(10);
System.out.println(s);
System.out.println("Longest Palindromic Substring:\n"+manacher(s));
}
}
It is called Manacher algorithm. For excellent explanation of Manacher algorithm see,
- Anonymous January 04, 2013leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
Also visit wiki page,
en.wikipedia.org/wiki/Longest_palindromic_substring