ℹ️ Select 'Choose Exercise', or randomize 'Next Random Exercise' in selected language.

Choose Exercise:
Timer 00:00
WPM --
Score --
Acc --
Correct chars --

Longest Palindromic Subsequence

Special / Other

Goal -- WPM

Ready
Exercise Algorithm Area
1func longestPalindromeSubsequence(s string) int {

2n := len(s)

3if n == 0 {

4return 0

5}

6if n == 1 {

7return 1

8}

9

10// dp[i][j] will store the length of the longest palindromic subsequence

11// for the substring s[i...j]

12dp := make([][]int, n)

13for i := range dp {

14dp[i] = make([]int, n)

15}

16

17// Base case: A single character is a palindrome of length 1

18for i := 0; i < n; i++ {

19dp[i][i] = 1

20}

21

22// Fill the DP table

23// Iterate over substring lengths (l)

24for l := 2; l <= n; l++ {

25// Iterate over starting indices (i)

26for i := 0; i <= n-l; i++ {

27// Calculate the ending index (j)

28j := i + l - 1

29

30// If the characters at the ends match

31if s[i] == s[j] {

32// If the substring length is 2, it's a palindrome of length 2

33if l == 2 {

34dp[i][j] = 2

35} else {

36// Otherwise, it's 2 plus the LPS of the inner substring

37dp[i][j] = dp[i+1][j-1] + 2

38}

39} else {

40// If the characters don't match, take the maximum of

41// excluding the first character or excluding the last character

42dp[i][j] = max(dp[i+1][j], dp[i][j-1])

43}

44}

45}

46

47// The result is the LPS of the entire string s[0...n-1]

48return dp[0][n-1]

49}

50

51// Helper function to find the maximum of two integers

52func max(a, b int) int {

53if a > b {

54return a

55}

56return b

57}
Algorithm description viewbox

Longest Palindromic Subsequence

Algorithm description:

This function calculates the length of the longest palindromic subsequence within a given string. A subsequence is formed by deleting zero or more characters from the original string, and a palindrome reads the same forwards and backward. This algorithm is useful in bioinformatics for sequence alignment and in text processing for finding commonalities between strings.

Algorithm explanation:

The algorithm uses dynamic programming to solve the Longest Palindromic Subsequence (LPS) problem. It builds a 2D table `dp` where `dp[i][j]` represents the length of the LPS for the substring `s[i...j]`. The base cases are single characters, which have an LPS length of 1. For longer substrings, if the characters at the ends `s[i]` and `s[j]` match, the LPS length is 2 plus the LPS of the inner substring `s[i+1...j-1]`. If they don't match, the LPS length is the maximum of the LPS of `s[i+1...j]` and `s[i...j-1]`. The time complexity is O(n^2) due to the nested loops filling the DP table, and the space complexity is also O(n^2) for the DP table. Edge cases like empty or single-character strings are handled explicitly. The correctness relies on the optimal substructure property: the LPS of a larger substring can be derived from the LPS of smaller, overlapping substrings.

Pseudocode:

function longestPalindromeSubsequence(s):
  n = length of s
  if n == 0: return 0
  if n == 1: return 1

  create a 2D array dp of size n x n, initialized to 0

  // Base case: single characters are palindromes of length 1
  for i from 0 to n-1:
    dp[i][i] = 1

  // Fill the dp table for substrings of length 2 to n
  for length from 2 to n:
    for i from 0 to n - length:
      j = i + length - 1
      if s[i] == s[j]:
        if length == 2:
          dp[i][j] = 2
        else:
          dp[i][j] = dp[i+1][j-1] + 2
      else:
        dp[i][j] = max(dp[i+1][j], dp[i][j-1])

  return dp[0][n-1]

function max(a, b):
  return a if a > b else b