Program Overview

This program calculates the length of the longest palindromic subsequence in a given string using dynamic programming. A palindromic subsequence is a sequence that appears in the same order when read forwards and backwards.

Program Structure

• Input: A string for which the longest palindromic subsequence needs to be found.
• Dynamic Programming Table: A 2D array to store lengths of longest palindromic subsequences for substrings of the given string.
• Output: The length of the longest palindromic subsequence.

C Program

#include 
#include 

// Function to find the length of the longest palindromic subsequence
int longestPalindromicSubseq(char *str) {
    int n = strlen(str);
    int dp[n][n]; // DP table

    // Initialize the table
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1; // Every single character is a palindrome of length 1
    }

    // Fill the table
    for (int length = 2; length <= n; length++) {
        for (int i = 0; i < n - length + 1; i++) { int j = i + length - 1; // Ending index of the substring if (str[i] == str[j]) { dp[i][j] = dp[i + 1][j - 1] + 2; // Characters match, include them in the count } else { dp[i][j] = (dp[i + 1][j] > dp[i][j - 1]) ? dp[i + 1][j] : dp[i][j - 1]; // Take the max from either case
            }
        }
    }

    return dp[0][n - 1]; // Return the length of the longest palindromic subsequence
}

// Main function
int main() {
    char str[100];

    // Input the string
    printf("Enter the string: ");
    scanf("%s", str);

    // Calculate the longest palindromic subsequence
    int length = longestPalindromicSubseq(str);
    printf("Length of Longest Palindromic Subsequence: %d\n", length);

    return 0;
}

Explanation of the Code

The program consists of two main parts: the function for calculating the longest palindromic subsequence and the main function to handle input and output:

• The longestPalindromicSubseq function implements the dynamic programming approach:
  • A 2D array dp is created to store the lengths of the longest palindromic subsequences for substrings of the input string.
  • The function initializes the table, setting the diagonal elements to 1 (since a single character is a palindrome).
  • It then iterates through all possible substrings and fills in the table based on whether the characters match or not.
• The main function handles user input:
  • The user is prompted to enter a string.
  • It calculates the length of the longest palindromic subsequence by calling the longestPalindromicSubseq function and displays the result.

Usage

To use the program:

1. Compile the program using a C compiler (e.g., gcc).
2. Run the executable and input the string.
3. The program will output the length of the longest palindromic subsequence.