Top 100
Longest Palindromic Subsequence
- Problem
- LC 516
- File
- top100_LC516LongestPalindromicSubsequence.java
- Path
- pkg5leetcode/top100/top100_LC516LongestPalindromicSubsequence.java
- Package
- pkg5leetcode.top100
- Command
- java pkg5leetcode/top100/top100_LC516LongestPalindromicSubsequence.java
- Approach
- DP on substrings: match or best of excluding ends.
- Complexity
- Time O(n^2), Space O(n^2)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.top100;2 3/*4 * Longest Palindromic Subsequence | LC 5165 * APPROACH: DP on substrings: match or best of excluding ends.6 * COMPLEXITY: Time O(n^2), Space O(n^2)7 */8public class top100_LC516LongestPalindromicSubsequence {9 static int longestPalindromeSubseq(String s) {10 int n = s.length();11 int[][] dp = new int[n][n];12 for (int i = n - 1; i >= 0; i--) {13 dp[i][i] = 1;14 for (int j = i + 1; j < n; j++) {15 if (s.charAt(i) == s.charAt(j))16 dp[i][j] = dp[i + 1][j - 1] + 2;17 else18 dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);19 }20 }21 return dp[0][n - 1];22 }23 24 public static void main(String[] args) {25 check(longestPalindromeSubseq("bbbab") == 4, "case1");26 check(longestPalindromeSubseq("cbbd") == 2, "case2");27 System.out.println("all tests passed");28 }29 30 static void check(boolean cond, String name) {31 if (!cond) throw new AssertionError("FAILED: " + name);32 System.out.println(" PASS " + name);33 }34}