Simple intuitive N^2 solution without using DP or mancaher or kmp algorithms


#1
int isPalindrome(int start1,int start2,string A) {
    int len = -1*(start1 == start2);
    while (start1>=0 && start2<A.size() && A[start1] == A[start2]) {
        start1--;
        start2++;
        len+=2;
    }
    return len;
}

string Solution::longestPalindrome(string A) {
    
    int maxStart = 0,maxLen = 1;
    for (int i=1;i<A.size();i++) {
        int len1 = isPalindrome(i,i,A);
        int start1 = i - (len1-1)/2;
        if (len1 > maxLen) {
            maxLen = len1;
            maxStart = start1;
        }
        int len2 = isPalindrome(i-1,i,A);
        int start2 = i - (len2/2);
        if (len2 > maxLen) {
            maxLen = len2;
            maxStart = start2;
        }
    }
    return A.substr(maxStart,maxLen);
}