This is the 12th day of my participation in the August More Text Challenge. For details, see:August is more challenging

The title

Given a string s, find the longest echo subsequence and return the length of that sequence.

A subsequence is defined as a sequence in which some characters or no characters are deleted without changing the order of the remaining characters.

The sample

Input: s = "bbBAB" Output: 4 Explanation: A possible longest echo subsequence is "BBBB". Input: s = "CBBD" Output: 2 Explanation: a possible longest echo subsequence is "bb".Copy the code

prompt

  • 1 <= s.length <= 1000
  • sConsists of lowercase letters only

Their thinking

  1. According to the definition of the subsequence, we need to find the longest return substring in the string S, which can be to remove the characters (left/right/both sides), keep only the continuous palindrome string in the middle, get the length of the string and return it.

  2. Palindrome string property: remove the first and last two characters, the rest of the string is still palindrome string, so when we encounter two equal characters I,j, we can use I +1, j-1 value to get the first length.

Code implementation

Method 1: dynamic programming

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for(int i = n - 1; i >= 0; --i){
            // The character itself counts as a palindrome of length 1
            dp[i][i] = 1;
            for(int j = i + 1; j < n; ++j){
                if(s.charAt(i) == s.charAt(j)){
                    // If two characters are equal, take the length of the middle palindrome + 2
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                }else{
                    // If they are not equal, take the longest value
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); }}}return dp[0][n - 1]; }}Copy the code

Method two: dynamic programming optimization

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for(int i = n - 2; i >= 0; --i){
            int pre = 0;
            for(int j = i + 1; j < n; ++j){
                int tmp = dp[j];
                if(s.charAt(i) == s.charAt(j)){
                    dp[j] = pre + 2;
                }else{
                    dp[j] = Math.max(dp[j], dp[j - 1]); } pre = tmp; }}return dp[n - 1]; }}Copy the code

The last

The article has the bad place that writes, ask big guy people not stingy give instruction, mistake is most can let a person grow, wish I and big guy the distance between shorten gradually!

If you think the article is helpful to you, please like, collect, follow, comment one key four connect support, your support is my creation biggest power!!

Source: leetcode-cn.com/problems/lo…