Longest Palindromic Substring + LinkedList O(1) & O(n)


#1

“”"
/**

  • Definition for singly-linked list.
  • struct ListNode {
  • int val;
    
  • ListNode *next;
    
  • ListNode(int x) : val(x), next(NULL) {}
    
  • };
    */

string longestPalindrome(string s) {
int length = s.length();
string ans = “”;
int max_length = 0;
//for odd length pallindrome
for(int mid = 0; mid<length; mid++){
for(int i=0; mid+i<length && mid-i>=0; i++){
if(s[mid-i] != s[mid+i]){
break;
}
int currentLength = 2*i + 1;
if(currentLength > max_length){
max_length = max(currentLength, max_length);
ans=s.substr(mid-i, currentLength);
}
}
}

    //for even length pallindrome
    for(int mid = 0; mid < length-1; mid++){
        for(int i=1; mid-i+1>=0 && mid+i<length; i++){
            if(s[mid-i+1] != s[mid+i]){
                break;
            }
            int currentLength = 2*i;
            if(currentLength > max_length){    
                max_length = max(currentLength, max_length);
                ans=s.substr(mid-i+1, currentLength);
            }
        }
    }
    return ans;
}

int Solution::solve(ListNode* A) {

string str = "";
while(A != NULL){
    str.push_back(A->val);
    A = A->next;
}
return longestPalindrome(str).size();

}

“”"