Leetcode discuss: Longest Palindromic Substring

 Here is the link. 

First practice | 2015-6-15 | C# | Dynamic programming

Jan. 30, 2021
I am working on preparation of Microsoft online assessment, and then work on a list algorithms on leetcode (5, 15, 23, 34, 38, 46, 49, 124, 127, 218, 240, 259). I had chance to review my own code written back in 2015 June 15.

Case study
It is hard to define a smart subproblem to avoid redundant calculation. The dynamic programming algorithm should be easy to write after the subproblem is clearly defined.

I thought about using two dimension array to market start and end position. But how to work on another subproblem? I could not figure out using length of the substring as a variable, and start from substring's length from 1 to length of the array.

Facts to review:

1. All substrings with one char is palindromic;
2. Any substring with length 2 should be easily checked if it is palindromic;
3. Any length after 2 should be easily defined by checking two ends of substring and then a subproblem.

Highlights of my code review:

1. I thought about how to solve the problem using two dimension array, but I could not figure out the idea in detail;
2. The idea is simple, two dimension array one is start position, and second one is end position of substring.
3. The challenge part is to start from length of substring, from 1 to n whereas n is the length of the string.

Time complexity:
Linear time O(N) - N is the length of the array

The following code was my practice back in 2015 June 15. I just could not believe that the algorithm is still challenge for me to figure out in less than 15 minutes.

public class Solution {
    public string LongestPalindrome(string s) {
        if (s == null)
		        return null;
 
	        if(s.Length <=1)
		        return s;
 
	        int maxLen = 0;
	        String longestStr = null;
 
	        int length = s.Length;
 
	        int[][] table = new int[length][];
            for (int i = 0; i < length; i++)
                table[i] = new int[length]; 

            //every single letter is palindrome
            for (int i = 0; i < length; i++)
            {
                table[i][i] = 1;
            }

	        //printTable(table);
 
	        //e.g. bcba
	        //two consecutive same letters are palindrome
	        for (int i = 0; i <= length - 2; i++) {
		        if (s[i] == s[i + 1]){
			        table[i][i + 1] = 1;
			        longestStr = s.Substring(i, 2);
		        }	
	        }

	        //printTable(table);

	        //condition for calculate whole table
	        for (int l = 3; l <= length; l++) {
		        for (int i = 0; i <= length-l; i++) {
			        int j = i + l - 1;

			        if (s[i] == s[j]) {
				        // how to ensure that table[i+1][j-1] is calculated before table[i][j] because the first one's length is j-i-2 whereas the second one is j-i. So, it is in the order. 
                        table[i][j] = table[i + 1][j - 1];

                        if (table[i][j] == 1 && l > maxLen)
                        {
                            longestStr = s.Substring(i, j + 1 - i);
                            maxLen = j + 1 - i; 
                        }
			        } else {
				        table[i][j] = 0;
			        }
			    
                   // printTable(table);
		        }
	        }
 
	        return longestStr;
    }      
}