Longest Palindromic Substring Solution

 Question: Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Solution :

Let us create a Table. If the string size is n, then the table will have n rows and n columns. The element a(i, j) of the table will determine whether the substring from index i to j is a palindrome or not. So in this way, we will calculate the maximum length of the palindromic substring. 

Now to fill this table we will use the following algorithm: 

STEP 1: Create a Table, Where the Row index is the start of the palindrome substring and the column index is the end of the palindromic substring.

STEP 2:  Fill the diagonal of the table with 1. Because (i, i) is itself a palindrome of length 1.

STEP 3: Fill (i, i+1) by checking adjacent characters. If they are equal then 1, else 0.

STEP 4: For every Distance other substrings of length > 2. You need to check two conditions :

    I. Is first and last, characters are equal : (s[i] == s[j])

   II.Is String inside a palindrome : (table[i+1][j-1] == 1)

If both the conditions are true then fill the table with 1, else 0.

STEP 5: Repeat step4 for every i, j with constant distance, then increment the distance.

Here is the solution : 

1. string longestPalindrome(string s) {
2. int maxLength = 1, n = s.size(), start=0;
3. int table[n][n] ;
4. memset( &table[0][0], 0, sizeof(table) );
5. for(int i =0; i < n; i++){
6. table[i][i] = 1;
7. }
8. for(int i = 0; i < n-1; i++){
9. if(s[i] == s[i+1]){
10. table[i][i+1] = 1;
11. maxLength =2;
12. start = i;
13. }
14. }
15. int dist ;
16. for(dist =2; dist < n; dist++){
17. for(int i = 0, j = i+dist; j<n; i++, j++ ){
18. if(s[i] == s[j] && table[i+1][j-1] == 1){
19. table[i][j] = 1;
20. if(j-i+1 > maxLength){
21. maxLength = j-i+1;
22. start = i;
23. }
24. }
25. }
26. }
27.  
28. string ans = "";
29. for(int i = start; i < start + maxLength; i++){
30. ans += s[i];
31. }
32. return ans;
33.  
34.  
35. }
36.