Longest Palindromic Substring Part I

November 20, 2011 in dynamic programming, string

Given a string S, find the longest palindromic substring in S.

This interesting problem has been featured in the famous Greplin programming challenge, and is asked quite often in the interviews. Why? Because this problem can be attacked in so many ways. There are five different solutions that I am aware of. Are you up to the challenge?

Head over to Online Judge to solve it now! (you may submit either C++ or Java solution)

Hint:
First, make sure you understand what a palindrome means. A palindrome is a string which reads the same in both directions. For example, “aba” is a palindome, “abc” is not.

A common mistake:
Some people will be tempted to come up with a quick solution, which is unfortunately flawed (however can be corrected easily):

Reverse S and become S’. Find the longest common substring between S and S’, which must also be the longest palindromic substring.

This seemed to work, let’s see some examples below.

For example,
S = “caba”, S’ = “abac”.
The longest common substring between S and S’ is “aba”, which is the answer.

Let’s try another example:
S = “abacdfgdcaba”, S’ = “abacdgfdcaba”.
The longest common substring between S and S’ is “abacd”. Clearly, this is not a valid palindrome.

We could see that the longest common substring method fails when there exists a reversed copy of a non-palindromic substring in some other part of S. To rectify this, each time we find a longest common substring candidate, we check if the substring’s indices are the same as the reversed substring’s original indices. If it is, then we attempt to update the longest palindrome found so far; if not, we skip this and find the next candidate.

This gives us a O(N²) DP solution which uses O(N²) space (could be improved to use O(N) space). Please read more about Longest Common Substring here.

Brute force solution, O(N³):
The obvious brute force solution is to pick all possible starting and ending positions for a substring, and verify if it is a palindrome. There are a total of C(N, 2) such substrings (excluding the trivial solution where a character itself is a palindrome).

Since verifying each substring takes O(N) time, the run time complexity is O(N³).

Dynamic programming solution, O(N²) time and O(N²) space:
To improve over the brute force solution from a DP approach, first think how we can avoid unnecessary re-computation in validating palindromes. Consider the case “ababa”. If we already knew that “bab” is a palindrome, it is obvious that “ababa” must be a palindrome since the two left and right end letters are the same.

Stated more formally below:

Define P[ i, j ] ← true iff the substring S_i … S_j is a palindrome, otherwise false.

Therefore,

P[ i, j ] ← ( P[ i+1, j-1 ] and S_i = S_j )

The base cases are:

P[ i, i ] ← true
P[ i, i+1 ] ← ( S_i = S_i+1 )

This yields a straight forward DP solution, which we first initialize the one and two letters palindromes, and work our way up finding all three letters palindromes, and so on…

This gives us a run time complexity of O(N²) and uses O(N²) space to store the table.

string longestPalindromeDP(string s) {
  int n = s.length();
  int longestBegin = 0;
  int maxLen = 1;
  bool table[1000][1000] = {false};
  for (int i = 0; i < n; i++) {
    table[i][i] = true;
  }
  for (int i = 0; i < n-1; i++) {
    if (s[i] == s[i+1]) {
      table[i][i+1] = true;
      longestBegin = i;
      maxLen = 2;
    }
  }
  for (int len = 3; len <= n; len++) {
    for (int i = 0; i < n-len+1; i++) {
      int j = i+len-1;
      if (s[i] == s[j] && table[i+1][j-1]) {
        table[i][j] = true;
        longestBegin = i;
        maxLen = len;
      }
    }
  }
  return s.substr(longestBegin, maxLen);
}

string longestPalindromeDP(string s) {

int n = s.length();

int longestBegin = 0;

int maxLen = 1;

bool table[1000][1000] = {false};

for (int i = 0; i < n; i++) {

table[i][i] = true;

}

for (int i = 0; i < n-1; i++) {

if (s[i] == s[i+1]) {

table[i][i+1] = true;

longestBegin = i;

maxLen = 2;

}

for (int len = 3; len <= n; len++) {

for (int i = 0; i < n-len+1; i++) {

int j = i+len-1;

if (s[i] == s[j] && table[i+1][j-1]) {

table[i][j] = true;

longestBegin = i;

maxLen = len;

}

return s.substr(longestBegin, maxLen);

}

Additional exercise:
Could you improve the above space complexity further and how?

A simpler approach, O(N²) time and O(1) space:
In fact, we could solve it in O(N²) time without any extra space.

We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only 2N-1 such centers.

You might be asking why there are 2N-1 but not N centers? The reason is the center of a palindrome can be in between two letters. Such palindromes have even number of letters (such as “abba”) and its center are between the two ‘b’s.

Since expanding a palindrome around its center could take O(N) time, the overall complexity is O(N²).

string expandAroundCenter(string s, int c1, int c2) {
  int l = c1, r = c2;
  int n = s.length();
  while (l >= 0 && r <= n-1 && s[l] == s[r]) {
    l--;
    r++;
  }
  return s.substr(l+1, r-l-1);
}

string longestPalindromeSimple(string s) {
  int n = s.length();
  if (n == 0) return "";
  string longest = s.substr(0, 1);  // a single char itself is a palindrome
  for (int i = 0; i < n-1; i++) {
    string p1 = expandAroundCenter(s, i, i);
    if (p1.length() > longest.length())
      longest = p1;

    string p2 = expandAroundCenter(s, i, i+1);
    if (p2.length() > longest.length())
      longest = p2;
  }
  return longest;
}

string expandAroundCenter(string s, int c1, int c2) {

int l = c1, r = c2;

int n = s.length();

while (l >= 0 && r <= n-1 && s[l] == s[r]) {

l--;

r++;

}

return s.substr(l+1, r-l-1);

}

string longestPalindromeSimple(string s) {

int n = s.length();

if (n == 0) return "";

string longest = s.substr(0, 1); // a single char itself is a palindrome

for (int i = 0; i < n-1; i++) {

string p1 = expandAroundCenter(s, i, i);

if (p1.length() > longest.length())

longest = p1;

string p2 = expandAroundCenter(s, i, i+1);

if (p2.length() > longest.length())

longest = p2;

}

return longest;

}

Further Thoughts:
Does an O(N) solution exist? You bet! However, it is not trivial and requires some very clever observation. The O(N) solution is explained in my next post.

» Continue reading Longest Palindromic Substring Part II.

Rating: 5.0/5 (4 votes cast)

Longest Palindromic Substring Part I, 5.0 out of 5 based on 4 ratings

← Regular Expression Matching

Longest Palindromic Substring Part II →

37 responses to Longest Palindromic Substring Part I

Programming Praxis said on November 11, 2011
I solved this problem at my blog.
VA:F [1.9.22_1171]
-1
Reply
- 1337c0d3r said on November 12, 2011
  Great job coding up the O(n) solution!
  VN:F [1.9.22_1171]
  0
  Reply
Daniel Sobral said on November 11, 2011
I solved it on codereview. I tried for a functional version with better than quadratic performance, since the one-liners were all quadratic.
http://codereview.stackexchange.com/questions/5241/more-functional-way-of-writing-this-palindrome-extractor/5260#5260
I’m afraid mine was definitely not one-liner. The first version was half the size of that, but code density was way too high.
VA:F [1.9.22_1171]
0
Reply
jcleetcode said on November 12, 2011
I also write a O(n) algorithm as Programming Praxis metioned in his URL. Submit to online judge system.
VN:F [1.9.22_1171]
0
Reply
vaibhav said on November 12, 2011
What about reversing the original string and then finding the longest common substring of both?
VA:F [1.9.22_1171]
0
Reply
Praveen said on November 12, 2011
@vaibhav that would not work. The string “abaaacedfaaabaxyz” would output “abaa” which is not the desired result.
VA:F [1.9.22_1171]
0
Reply

durbin said on November 16, 2011

String longestPalindrome(String s) {
      int len = s.length();          
      if (len == 0) {
    	  return null;
      }
      
      int maxPalindromeLen = 0;
      int centerPos = 0;
      
	  // check palindrome centered at s[i]
      for (int i = 0; 2*(len - i) - 1 > maxPalindromeLen; i++) {
    	  int tmpLen = 0;
    	  int j = 0; 

    	  while (j <=i && (i + j)  maxPalindromeLen) {
     		  maxPalindromeLen = tmpLen;
     		  centerPos = i;
     	  }
    	  }
      } 
	  
      // check palindrome centered at s[i] and s[i+1]          
      for (int i = 0; 2*(len - i) -2 > maxPalindromeLen; i++) {
    	  int j = 0;
    	  int tmpLen = 0;
    	  while (j <=i && (i + j + 1)  maxPalindromeLen) {
     		  maxPalindromeLen = tmpLen;
     		  centerPos = i;
     	  }
    	  }
    	  
      }
      
      return s.substring(centerPos-(maxPalindromeLen -1)/2, centerPos+maxPalindromeLen/2 + 1);
}

String longestPalindrome(String s) {

int len = s.length();

if (len == 0) {

return null;

}

int maxPalindromeLen = 0;

int centerPos = 0;

// check palindrome centered at s[i]

for (int i = 0; 2*(len - i) - 1 > maxPalindromeLen; i++) {

int tmpLen = 0;

int j = 0;

while (j <=i && (i + j) maxPalindromeLen) {

maxPalindromeLen = tmpLen;

centerPos = i;

}

// check palindrome centered at s[i] and s[i+1]

for (int i = 0; 2*(len - i) -2 > maxPalindromeLen; i++) {

int j = 0;

int tmpLen = 0;

while (j <=i && (i + j + 1) maxPalindromeLen) {

maxPalindromeLen = tmpLen;

centerPos = i;

}

return s.substring(centerPos-(maxPalindromeLen -1)/2, centerPos+maxPalindromeLen/2 + 1);

}

wayne said on November 16, 2011

I think that mine is linear.

import java.util.*;
public class palindromeSolution{
    public static String input="adfasdfcabbacdfadsfasdfa";
    public static Map statistic = new HashMap();
    public static Map allPalinDromes = new HashMap();

    public static void main(String[] args){
	    prepareInfo();
	    //System.out.println("shang:statistic:"+statistic);
	    pickPalinDromes();
	}
	public static void prepareInfo(){
	    for(int i=0;i&lt;input.length();i++){
		    char a = input.charAt(i);
		    //System.out.println(&quot;shang:char:&quot;+a);
		    List positions = (List) statistic.get(Character.toString(a));
		    if(positions == null){
			    positions = new ArrayList();
			}
			positions.add(i);
			statistic.put(Character.toString(a),positions);

		}
	}
	public static void pickPalinDromes(){
	    for(Object entry:  statistic.entrySet()){
		   String endChar = (String) ((Map.Entry)entry).getKey();
		   List positions = (List) ((Map.Entry)entry).getValue();
		   if(positions.size()&lt;=1){
		       continue;
		   }
		   loopThroughPositions(positions);
		}
	}
	public static void loopThroughPositions(List positions){
		    for(int i=0;i&lt;positions.size();i++){
			   if(i==positions.size()){
			       continue;
			   }
			   Integer start = (Integer) positions.get(i);
               for(int ii=i+1;ii2){
				       continue;
				   }
			       findMaxPalinDrome(start,endd);


			   }

			}
	}
	public static void findMaxPalinDrome(Integer start, Integer endd){
		boolean stopFlag = true;
       	while(stopFlag){
		   start--;
		   endd++;
		   if(start&lt;0){
		       continue;
		   }
		   char startChar = input.charAt(start);
		   char endChar = input.charAt(endd);
		   if(startChar != endChar){
		       stopFlag=false;
		       allPalinDromes.put(start+1,endd-1);
		       System.out.println(&quot;yes, we found one:&quot;+input.substring(start+1,endd));
		   }

		}
    }
}

import java.util.*;

public class palindromeSolution{

public static String input="adfasdfcabbacdfadsfasdfa";

public static Map statistic = new HashMap();

public static Map allPalinDromes = new HashMap();

public static void main(String[] args){

prepareInfo();

//System.out.println("shang:statistic:"+statistic);

pickPalinDromes();

}

public static void prepareInfo(){

for(int i=0;i<input.length();i++){

char a = input.charAt(i);

//System.out.println("shang:char:"+a);

List positions = (List) statistic.get(Character.toString(a));

if(positions == null){

positions = new ArrayList();

}

positions.add(i);

statistic.put(Character.toString(a),positions);

}

public static void pickPalinDromes(){

for(Object entry: statistic.entrySet()){

String endChar = (String) ((Map.Entry)entry).getKey();

List positions = (List) ((Map.Entry)entry).getValue();

if(positions.size()<=1){

continue;

}

loopThroughPositions(positions);

}

public static void loopThroughPositions(List positions){

for(int i=0;i<positions.size();i++){

if(i==positions.size()){

continue;

}

Integer start = (Integer) positions.get(i);

for(int ii=i+1;ii2){

continue;

}

findMaxPalinDrome(start,endd);

}

public static void findMaxPalinDrome(Integer start, Integer endd){

boolean stopFlag = true;

while(stopFlag){

start--;

endd++;

if(start<0){

continue;

}

char startChar = input.charAt(start);

char endChar = input.charAt(endd);

if(startChar != endChar){

stopFlag=false;

allPalinDromes.put(start+1,endd-1);

System.out.println("yes, we found one:"+input.substring(start+1,endd));

}

rachel said on November 17, 2011

Java version:

public String longestPalindrome(String s)
	{
		char[] c = s.toCharArray(); 
		int maxLen = 0, len=0;
		int begin = 0;
		for(int k=0;k=0 &amp;&amp; k+len+1 maxLen)
			{
				begin = k-(len-1)-1;
				maxLen = len*2+1;
			}
			len = 0;
			while(k&gt;=len &amp;&amp; k+len+1 maxLen)
			{
				begin = k-(len-1);
				maxLen = len*2;
			}	
		}
		return new String(c,begin,maxLen);
	}

public String longestPalindrome(String s)

{

char[] c = s.toCharArray();

int maxLen = 0, len=0;

int begin = 0;

for(int k=0;k=0 && k+len+1 maxLen)

{

begin = k-(len-1)-1;

maxLen = len*2+1;

}

len = 0;

while(k>=len && k+len+1 maxLen)

{

begin = k-(len-1);

maxLen = len*2;

}

return new String(c,begin,maxLen);

}

rachel said on November 17, 2011

public String longestPalindrome(String s)
{
		char[] c = s.toCharArray(); 
		int maxLen = 0, len=0;
		int begin = 0;
		for(int k=0;k<s.length()-1;k++)
		{
			len = 0;
			while(k-len-1>=0 && k+len+1<s.length() && c[k-len-1]==c[k+len+1])
			{
				len+=1;
			}
			if(len*2+1 > maxLen)
			{
				begin = k-(len-1)-1;
				maxLen = len*2+1;
			}
			len = 0;
			while(k>=len && k+len+1<s.length() && c[k-len]==c[k+len+1])
			{
				len+=1;
			}
			if(len*2 > maxLen)
			{
				begin = k-(len-1);
				maxLen = len*2;
			}	
		}
		return new String(c,begin,maxLen);
}

public String longestPalindrome(String s)

{

char[] c = s.toCharArray();

int maxLen = 0, len=0;

int begin = 0;

for(int k=0;k<s.length()-1;k++)

{

len = 0;

while(k-len-1>=0 && k+len+1<s.length() && c[k-len-1]==c[k+len+1])

{

len+=1;

}

if(len*2+1 > maxLen)

{

begin = k-(len-1)-1;

maxLen = len*2+1;

}

len = 0;

while(k>=len && k+len+1<s.length() && c[k-len]==c[k+len+1])

{

len+=1;

}

if(len*2 > maxLen)

{

begin = k-(len-1);

maxLen = len*2;

}

return new String(c,begin,maxLen);

}

1337c0d3r said on November 17, 2011
@durbin @wayne @rachel I just added syntax highlighting for your code. This is an experimental feature. Just FYI, you can syntax highlight using [lang]your code here…[/lang]. Replace lang with your favorite language, in this case, lang=java.
VN:F [1.9.22_1171]
0
Reply
- quasar said on December 6, 2011
  Is a single char a palindrome? And I think there is a bug in your second solution. When there is a single char string input, the expandAroundCenter() will return s.substr(1, 0). Is that correct?
  VA:F [1.9.22_1171]
  0
  Reply
  - 1337c0d3r said on December 6, 2011
    Very good observation. I missed that completely.
    If you notice carefully however, the code still runs fine. In C++, for a single char string input, s.substr(1,0) returns an empty string. In general, for s with length of n, s.substr(n, k) will always return an empty string for k >= 0.
    http://www.cplusplus.com/reference/string/string/substr/
    However, my code is not written in a good way. Good code should reflect clearly its intentions. Even though it does work, it is highly misleading as it seem like it is out of bounds. Thanks, and I have refined the code.
    VN:F [1.9.22_1171]
    0
    Reply
    - garima said on April 13, 2012
      Pls correct me if I am wrong here..
      If we enter single character, we are not going to enter in the for loop itself as length is 1 then and the loop condition
      i=0; i<n-1; i++
      restricts to enter.
      Then, how come expandAroundCenter() function is called?
      VA:F [1.9.22_1171]
      0
      Reply
Prongs said on November 18, 2011
In JAVA, O(n*n):
public class Palindrome {
public static void main(String[] args) throws IOException {
int min=-1;
String s,sub,rev;
StringBuffer temp;
ArrayList arr = new ArrayList();
int len;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println(“Enter a string”);
s = br.readLine();
if(s.length() == 0)
System.out.println(“None”);
len = s.length();
for(int i = 0; i < len; i++)
{
for(int j = i; j <= len; j++)
{
sub = s.substring(i,j);
if(sub.length() min){
min=sub.length();
arr.add(sub);
}
}
}
}
System.out.println(“Substring with longest palindrome – “+arr.get((arr.size()-1)));
}
}
VA:F [1.9.22_1171]
0
Reply
Qi Li said on December 21, 2011
string longestPalindrome(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
// NO #include’s are required
if (s.size() == 1) {
return s;
}
string t = “”;
for (int i = 1; i = 0 && (i + j + 1) t.size()) {
t = r;
}
j = 0;
while (s[i - 1 - j] == s[i + j] &&
(i – 1 – j) >= 0 && (i + j) t.size()) {
t = r;
}
}
return t;
}
VA:F [1.9.22_1171]
0
Reply
Razor said on February 17, 2012
I think there is a bug in your 2nd code again, Say when s = “abba” and i = 1 . I come to p2 expandString takes(s,1,2) and in the while loop l becomes -1 and r becomes 4
So when returning the substring u return s.substr(-1+1,4-(-1+1)) = s.substr(0,4) which is out of bounds.
VA:F [1.9.22_1171]
0
Reply
- 1337c0d3r said on February 17, 2012
  s.substr(0,4) returns “abba”, which means start at index 0 and its length is 4.
  VN:F [1.9.22_1171]
  0
  Reply
Razor said on February 17, 2012
it should be while(l > 0 && r < n-1 && s[l] == s[r])
VA:F [1.9.22_1171]
0
Reply
- 1337c0d3r said on February 17, 2012
  If you do this you would not compare the two characters at the end for equality. This would miss out some palindromes.
  VN:F [1.9.22_1171]
  0
  Reply
Razor said on February 17, 2012
and also return s.substr(l,r-l-1)
VA:F [1.9.22_1171]
0
Reply
Neevan said on March 16, 2012
Thnx for clear explanation….
VA:F [1.9.22_1171]
0
Reply
Neevan said on March 16, 2012
Thnx for succinct explanation….
VA:F [1.9.22_1171]
0
Reply
Naveen said on March 16, 2012
Hey 1337c0d3r,
Being a non-native English speaker i find one para little confusing ..could you please rephrase the below paragraph in simple English ..Thank you in advance…
” We could see that the longest common substring method fails when there exists this ……… ” till the end of that paragraph ..particularly what do you mean by this “a reversed copy of a non-palindromic substring in some other part of S”…
VA:F [1.9.22_1171]
0
Reply
Shundan Xiao said on May 4, 2012
Hi, I think there is a bug in this method:
string expandAroundCenter(string s, int c1, int c2) {
// that’s what to added to make it correct. otherwise if you have
//s=”bc”, c1=0 and c2=1, you won’t be able to get into the while
//loop, but when you return, you are returning based on the
//modified index.
if(s[c1]!=s[c2]){
return “”;
}
int l = c1, r = c2;
int n = s.length();
while (l >= 0 && r <= n-1 && s[l] == s[r]) {
l–;
r++;
}
return s.substr(l+1, r-l-1);
}
VN:F [1.9.22_1171]
0
Reply
Omar Mohammad Othman said on May 7, 2012
Could you please explain this paragraph again? I really didn’t get it…
To rectify this, each time we find a longest common substring candidate, we check if the substring’s indices are the same as the reversed substring’s original indices. If it is, then we attempt to update the longest palindrome found so far; if not, we skip this and find the next candidate.
VA:F [1.9.22_1171]
0
Reply
Rohit said on May 7, 2012
The DP method fails for your counterexample in the beginning of the article. Try “abartaba”
VA:F [1.9.22_1171]
0
Reply
reader said on May 26, 2012
I can not understand the table[1000][1000]
Why 1000? How did you come up with 1000?Could you please explain?
VA:F [1.9.22_1171]
0
Reply

Sherry said on June 21, 2012

I have a solution and passed all the test cases, I used two for loops and a recursive function inside the second loop, does this mean this is O(N3) in time??But my space is O(1), I think. Here is my code:

class Solution {
public:
    string longestPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        int firstIndex=0,lastIndex=0,nextFIndex = 0,nextLIndex=0;
        
        if(s.length() == 1)
            return s;
        else
        {
            for(int i=0; i < s.length()-1; i++)
            {
                nextFIndex = i;
                nextLIndex = 0;
                for(int j=s.length()-1; j>i; j--)
                {
                    if(IsPalindrome(s, i, j))
                    {
                        nextLIndex = j;
                        break;
                    }
                }
                
                if(nextLIndex!=0 && (nextLIndex-nextFIndex+1 > lastIndex-firstIndex+1))
                {
                    firstIndex = nextFIndex;
                    lastIndex = nextLIndex;
                }
            }
            
            if(lastIndex != 0)
                return s.substr(firstIndex, lastIndex-firstIndex+1);
            else
                return "";
        }
        
    }
    
private:
    bool IsPalindrome(string& s, int firstIndex, int lastIndex)
    {
        if(s[firstIndex] == s[lastIndex])
        {
            if(firstIndex == lastIndex || (firstIndex+1)==lastIndex)
                return true;
            else 
                return IsPalindrome(s, firstIndex+1, lastIndex-1);
        }
        else
            return false;
    }
    
};

class Solution {

public:

string longestPalindrome(string s) {

// Start typing your C/C++ solution below

// DO NOT write int main() function

int firstIndex=0,lastIndex=0,nextFIndex = 0,nextLIndex=0;

if(s.length() == 1)

return s;

else

{

for(int i=0; i < s.length()-1; i++)

{

nextFIndex = i;

nextLIndex = 0;

for(int j=s.length()-1; j>i; j--)

{

if(IsPalindrome(s, i, j))

{

nextLIndex = j;

break;

}

if(nextLIndex!=0 && (nextLIndex-nextFIndex+1 > lastIndex-firstIndex+1))

{

firstIndex = nextFIndex;

lastIndex = nextLIndex;

}

if(lastIndex != 0)

return s.substr(firstIndex, lastIndex-firstIndex+1);

else

return "";

}

private:

bool IsPalindrome(string& s, int firstIndex, int lastIndex)

{

if(s[firstIndex] == s[lastIndex])

{

if(firstIndex == lastIndex || (firstIndex+1)==lastIndex)

return true;

else

return IsPalindrome(s, firstIndex+1, lastIndex-1);

}

else

return false;

}

};

grubbyfan said on September 15, 2012
java version, passed both small and large,
running time is n^2 , O(1) space
public String longestPalindrome(String s) {
int frontIndex = 0;
int backIndex = 0;
for (int i = 1; i = 0 && front frontIndex – backIndex + 1) {
frontIndex = front – 1;
backIndex = back + 1;
}
}
back = i – 1; front = i;
if (front + 1 = 0 && front + 1 frontIndex – backIndex + 1) {
backIndex = back + 1;
frontIndex = front;
}
}
}
String str = s.substring(backIndex, frontIndex + 1);
return str;
}
VN:F [1.9.22_1171]
0
Reply
grubbyfan said on September 15, 2012
public String longestPalindrome(String s) {
int frontIndex = 0;
int backIndex = 0;
for (int i = 1; i = 0 && front frontIndex – backIndex + 1) {
frontIndex = front – 1;
backIndex = back + 1;
}
}
back = i – 1; front = i;
if (front + 1 = 0 && front + 1 frontIndex – backIndex + 1) {
backIndex = back + 1;
frontIndex = front;
}
}
}
String str = s.substring(backIndex, frontIndex + 1);
return str;
}
VN:F [1.9.22_1171]
0
Reply
Ashwani Kumar said on November 5, 2012
Hello:
I am not able to get the following lines
“You might be asking why there are 2N-1 but not N centers? The reason is the center of a palindrome can be in between two letters.” Here, I am not clear why there are 2N-1 centers. Can somebody explain with some example?
VA:F [1.9.22_1171]
0
Reply
Aks said on January 3, 2013
The total number of brute force strings are not nc2. You have mentioned in the brute force solution as total number of substrings are nc2 which is incorrect.
VA:F [1.9.22_1171]
0
Reply
- Aks said on January 3, 2013
  I think they are
  nc1 + Sum ( i = 1 to n-1) (nci) / 2 + ncn
  where nci = n combination i
  VA:F [1.9.22_1171]
  0
  Reply
Mony Sim said on January 20, 2013
This is the shortest solution.
bool isPalindrome(string s){
int i=0;
int len=s.length();
while(i<len/2)
{
if(s[i]!=s[len-i-1)
return false;
}
return true;
}
VN:F [1.9.22_1171]
0
Reply
Mony Sim said on January 20, 2013
This is the shortest solution.
bool isPalindrome(string s){
int i=0;
int len=s.length();
while(i<len/2)
{
if(s[i]!=s[len-i-1)
return false;
i++;
}
return true;
}
VN:F [1.9.22_1171]
0
Reply
- Kahn said on February 25, 2013
  you sure get the title correctly?
  VN:F [1.9.22_1171]
  0
  Reply