Program Explanation

The longest palindromic subsequence problem involves finding the longest sequence within a string that
reads the same forward and backward. This program uses dynamic programming to compute the length of the
longest palindromic subsequence efficiently.

Program Structure

1. Function Definition: The main function is longestPalindromicSubsequence(s string) int,
   which takes a string as input and returns the length of the longest palindromic subsequence.
2. Dynamic Programming Table: A 2D slice dp is created to store the lengths
   of palindromic subsequences for substrings.
3. Logic: Nested loops iterate through the string:
   • Single characters are palindromes of length 1.
   • For each pair of characters, the program checks if they match:
     • If they match, the length is updated based on the inner substring.
     • If they don’t match, it takes the maximum from the adjacent substrings.
4. Result: The length of the longest palindromic subsequence is found in the top-right
   cell of the DP table.

Go Code

package main

import (
    "fmt"
)

// longestPalindromicSubsequence finds the length of the longest palindromic subsequence.
func longestPalindromicSubsequence(s string) int {
    n := len(s)
    // Create a DP table to store lengths of palindromic subsequences
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    
    // Every single character is a palindrome of length 1
    for i := 0; i < n; i++ {
        dp[i][i] = 1
    }
    
    // Fill the DP table
    for length := 2; length <= n; length++ {
        for i := 0; i < n-length+1; i++ { j := i + length - 1 if s[i] == s[j] { dp[i][j] = dp[i+1][j-1] + 2 } else { dp[i][j] = max(dp[i][j-1], dp[i+1][j]) } } } // The length of the longest palindromic subsequence return dp[0][n-1] } // max returns the maximum of two integers. func max(a, b int) int { if a > b {
        return a
    }
    return b
}

func main() {
    // Example string
    s := "BBABCBCAB"
    
    length := longestPalindromicSubsequence(s)
    fmt.Printf("Length of Longest Palindromic Subsequence: %d\n", length)
}

Explanation of the Code:

• Function longestPalindromicSubsequence(s string) int:
  • This function computes the length of the longest palindromic subsequence in the given string using dynamic programming.
  • It initializes a 2D slice dp, where dp[i][j] holds the length of the longest palindromic subsequence in the substring from index i to j.
• Dynamic Programming Table (dp):
  • The dimensions of the dp table are n x n, where n is the length of the input string.
  • The diagonal elements are initialized to 1 since single characters are palindromic.
• Logic for Filling the DP Table:
  • The outer loop iterates through possible lengths of substrings.
  • The inner loop checks each substring starting at index i and ending at index j.
  • If the characters at both ends (s[i] and s[j]) are equal, the value from the inner substring is taken and incremented by 2.
  • If they are not equal, the program takes the maximum length from the adjacent substrings.
• Function max(a, b int) int:
  • A utility function that returns the maximum of two integers.

How to Run the Program:

1. Save the code as main.go.
2. Open your terminal and navigate to the directory containing the file.
3. Run the command go run main.go.

This program effectively demonstrates the solution to finding the longest palindromic subsequence using dynamic programming and can serve as a useful reference for various applications.

Conclusion

This Go program efficiently calculates the length of the longest palindromic subsequence using dynamic
programming. The algorithm has a time complexity of O(n^2), where n is the length of the input string.
This method is useful in various applications, such as bioinformatics and text processing, where
identifying palindromic sequences is essential.