Search⌘ K
Home
Courses
Algorithms for Coding Interviews in C#

Solution: Longest Palindromic Subsequence

Explore dynamic programming techniques to find the longest palindromic subsequence in a string. Understand brute force, memoization, and bottom-up approaches, including how to optimize recursive calls and use lookup tables, while analyzing time and space complexity for each solution.

We'll cover the following...

Solution 1: Brute force

C# 9.0
using System;
class Program
{
    /// <summary>
    /// Finds the length of the longest palindromic subsequence.
    /// </summary>
    /// <param name="s">Input string.</param>
    /// <param name="startIndex">Starting index of the sequence.</param>
    /// <param name="endIndex">Ending index of the sequence.</param>
    /// <returns>Length of longest palindromic subsequence.</returns>
    static int LongestPalindromicSubsequenceRecursive(string s, int startIndex, int endIndex)
    {
        if (startIndex > endIndex)
            return 0;
        // Every sequence with one element is a palindrome of length 1
        if (startIndex == endIndex)
            return 1;
        // Case 1: elements at the beginning and the end are the same
        if (s[startIndex] == s[endIndex])
            return 2 + LongestPalindromicSubsequenceRecursive(s, startIndex + 1, endIndex - 1);
        // Case 2: skip one element either from the beginning or the end
        int c1 = LongestPalindromicSubsequenceRecursive(s, startIndex + 1, endIndex);
        int c2 = LongestPalindromicSubsequenceRecursive(s, startIndex, endIndex - 1);
        return Math.Max(c1, c2);
    }
    /// <summary>
    /// Finds the length of the longest palindromic subsequence.
    /// </summary>
    /// <param name="s">Input string.</param>
    /// <returns>Length of longest palindromic subsequence.</returns>
    static int LongestPalindromicSubsequence(string s)
    {
        return LongestPalindromicSubsequenceRecursive(s, 0, s.Length - 1);
    }
    // Driver code to test the above method
    static void Main(string[] args)
    {
        Console.WriteLine(LongestPalindromicSubsequence("cddpd"));
        Console.WriteLine(LongestPalindromicSubsequence("abdbca"));
        Console.WriteLine(LongestPalindromicSubsequence("cddpd"));
        Console.WriteLine(LongestPalindromicSubsequence("pqr"));
    }
}

Explanation

By now, you must have noticed a pattern in the way we approach dynamic programming problems.

In this brute-force solution, we do the following:

  • If the element at the beginning and the end are the same, we increase our count by two and make a recursive call for the remaining sequence (lines 22–23).
  • Otherwise, we skip the element either from the beginning or the end to make two recursive calls for the remaining subsequence. After that, we return the greater result (lines 26–27).

Time complexity

The time complexity of the above algorithm is exponential O(2n)O(2^n), where nn is the length of the input sequence. The space complexity is O(n)O(n), which is the maximum number of ...