s = "madamracecarbob"
//some validations here
1. start=0, min=0,max=0
//min and max will store the longest palindrome
//start and and end index
2. for all characters from i to N
//below will take care for a string like 'madam'
//we will vitualize to understand this better
3. int a = expand(s,start,start)
//below will take care for a string like 'appa'
//we will vitualize to understand this better
4. int b = expand(s,start,start+1)
// we get the longest 'index'
int len = max(a,b)
//updating min and max only when we have a longest
//palindrome, i.e. when len > (max-min)
//you will understand why len > (max-min)
5. if(len > (max-min)
6. update min and max
//remember, our 'i' is growing
//in the case of bob, expand gave us 3 and i = 1
//start= 1-(3-1)/2 = 1-2/2 = 1-1 = 0
//end= 1+(3/2) = 1+(1)=2
7. min = new min value (i-(len-1)/2)//0
8. max = new max value (i + (len/2)) //2
//we will see why end+1 soon
//remember the below is substring and should not
//be confused with array[index]
//substring works from startIndex to endIndex+1
9. return s.sub(start,end+1)//0,3
//-------------
expand(s, start, end)
//some validations here
1. while (start >= 0 and end < N and
character at 'start' is equal to character
at 'end')
//the above condation is true for
//'p' and 'p' in 'appa' and index 1 and 2 (start,end)
//and for 'o' in 'bob' at index 1 and 1 (start,end)
2. start-- and end ++
//we found a pontential palindrome
//we check the next characters, this is where we expand from center. for 'bob' at i = 1
//we will check 'b' and 'b' before start and end growing beyound our limits, start >= 0 and end < new
//return the max 'index' where the loop exited
//after getting longest palindrome
//this index will be end - start -1
//we will later and 1 to our max
//let see why the below by an example
//we start by 'bob' at start=end=1 = 'o'
//first:
// - start = 1, end = 1
// - start-- end++
// start = 0, = end = 2
// s[start] = s[end= >> 'b = b'
//check[start-- end++, start = -1, end = 3 >> break]
//we break at start = -1 and end = 3
//what is the last index?
//we can say 3 - (-1) - 1 = 3
return end - start - 1;
//go back to 5-9 for better understanding
//After understanding the process
//Let's now analyze the below
s = "madamracecarbob"
/**
0,0 >> 'm'our longest palindrome
0,1 >> not a palindrome
1,1 >> 'a' >> 0,2 = m and d >> not a palindrome
1,2 >> not a palindrome
2,2 >> 'd' >> 1,3 ok >> 0,4 ok >> -1,5 break
end = (right - left -1) = 5 - (-1) - 1 = 5
we have new longest palindrome 0,5 and i = 2
min = (i-(len-1)/2)
max = (i + (len/2))
min = 2 - (5-1)/2 = 2 - (4/2) = 0
max = 2 + (5/2) = 2 + 2 = 4
longest palindrome is s.sub(0,4+1)
2,3 >> not palindrome
3,3 >> 'a' >> 2,4 not a palindrome
3,4 >> not a palindrome
4,4 >> 'm' >> 3,5 not a palindrome
5,5 >> 'r' >> 4,6 not a palindrome
5,6 >> not a palindrome
6,6 >> 'a' >> 5,7 not a palindrome
6,7 >> not a palindrome
7,7 >> 'c' ,6,7 not a palindrome
8,8 >> 'e' >> 7,9 ok >> 6,10 ok >> 5,11 ok >> 4,12 break
end at 4,12 since 'm' and 'b' are not equal
end = (right - left -1)
end = (12 - 4 - 1) = 7 and i was 8
Previously
min = 0 and max = 4
len > (max-min), 7 > (4-0) , we will update min/max
min = (i-(len-1)/2)
min = (8-(7-1)/2) = 8 - 6/2 = 8 - 3 = 5
max = (i + (len/2))
max = (8 + (7/3)) = 8 + 3 = 11
min = 5, max = 11
The process will continue till end of the string
8,9 >> not a palindrome
... continue
s = "m,a,d,a,m,r,a,c,e,c,a, r, b, o, b"
0,1,2,3,4,5,6,7,8,9,10,11,12,13,14
*/
//Sample code
public class MyClass {
public static void main(String[] args) {
String s = "bobracecarmadam";
char[] arr = s.toCharArray();
int n = arr.length;
int max = 0, min = 0;
for(int i=0;i
int a = expand(arr, n, i, i);
int b = expand(arr, n, i, i+1);
int len = Math.max(a, b);
if(len > (max-min)) {
min = i - (len -1)/2;
max = i + (len/2);
}
}
String longest = s.substring(min, max+1);
System.out.println("longest = " +longest);
}
private static int expand(char[] arr, int n, int left, int right) {
while(left >= 0 && right < n && arr[left] == arr[right]) {
left--; right++;
}
return right - left - 1;
}
}