Length of Longest Palindrome in Linked List

Slug: length-of-longest-palindrome-in-linked-list Difficulty: Medium Id: 700461 Topic Tags: Linked List, palindrome, Data Structures Company Tags: Accolite, Microsoft

Summary

Given a linked list, find the length of the longest palindromic subsequence that can be formed by traversing the linked list. A palindrome is a sequence that reads the same backward as forward.

Detailed Explanation

The problem involves identifying the longest palindromic subsequence in a linked list. To solve this, we will first traverse the linked list to build a string representation of it. Then, we will use dynamic programming to find the length of the longest palindrome that can be formed by selecting characters from the string.

Here's a step-by-step breakdown of the solution:

Traverse the linked list and build a string representation of it.
Initialize a 2D array dp with dimensions (n x n), where n is the length of the string.
Fill the dp array in a bottom-up manner:
- For each character at index i in the string, check if the character at index j (where j = n-1-i) matches it.
- If they match, set dp[i][n-1-i] to dp[i+1][n-2-i] + 2, as we have found a palindrome of length 2 centered at the current character.
- If they don't match, set dp[i][n-1-i] to the maximum of dp[i+1][n-1-i] and dp[i][n-2-i].
The length of the longest palindromic subsequence is stored in the top-right corner of the dp array, i.e., dp[0][n-1].

Time complexity: O(n^2), where n is the length of the linked list. Space complexity: O(n^2), as we need to store the dp array.

Optimized Solutions

Java

public class Main { public static int longestPalindromeLength(LinkedListNode node) { StringBuilder sb = new StringBuilder(); while (node != null) { sb.append(node.data); node = node.next; } String str = sb.toString(); int n = str.length(); boolean[][] dp = new boolean[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j <= i; j++) { if (str.charAt(i) == str.charAt(n-1-j)) { dp[i][j] = (i - j < 2 || dp[i-1][j+1]) ? true : false; } else { dp[i][j] = dp[i-1][j] || dp[i][j+1]; } } } int length = 0; for (int i = 0; i < n; i++) { if (dp[i][0]) { length = i + 1; break; } } return length; } public static void main(String[] args) { // Example usage: LinkedListNode node = new LinkedListNode(1); node.next = new LinkedListNode(2); node.next.next = new LinkedListNode(3); node.next.next.next = new LinkedListNode(4); node.next.next.next.next = new LinkedListNode(5); node.next.next.next.next.next = new LinkedListNode(6); System.out.println(longestPalindromeLength(node)); // Output: 2 } } class LinkedListNode { int data; LinkedListNode next; public LinkedListNode(int data) { this.data = data; this.next = null; } }