Skip to main content
Talentd

Longest Palindromic Path in Graph - Solution & Explanation

HardStringDynamic ProgrammingBit ManipulationGraph4 min readAsked at: Google
Practice this problem

Problem Statement

You are given an integer n and an undirected graph with n nodes labeled from 0 to n - 1 and a 2D array edges, where edges[i] = [ui, vi] indicates an edge between nodes ui and vi.

You are also given a string label of length n, where label[i] is the character associated with node i.

You may start at any node and move to any adjacent node, visiting each node at most once.

Return the maximum possible length of a palindrome that can be formed by visiting a set of unique nodes along a valid path.

 

Example 1:

Input: n = 3, edges = [[0,1],[1,2]], label = "aba"

Output: 3

Explanation:

  • The longest palindromic path is from node 0 to node 2 via node 1, following the path 0 → 1 → 2 forming string "aba".
  • This is a valid palindrome of length 3.

Example 2:

Input: n = 3, edges = [[0,1],[0,2]], label = "abc"

Output: 1

Explanation:

  • No path with more than one node forms a palindrome.
  • The best option is any single node, giving a palindrome of length 1.

Example 3:

Input: n = 4, edges = [[0,2],[0,3],[3,1]], label = "bbac"

Output: 3

Explanation:

  • The longest palindromic path is from node 0 to node 1, following the path 0 → 3 → 1, forming string "bcb".
  • This is a valid palindrome of length 3.

 

Constraints:

  • 1 <= n <= 14
  • n - 1 <= edges.length <= n * (n - 1) / 2
  • edges[i] == [ui, vi]
  • 0 <= ui, vi <= n - 1
  • ui != vi
  • label.length == n
  • label consists of lowercase English letters.
  • There are no duplicate edges.

Approach Overview

Problem Overview: You are given a graph where each node (or edge) contributes a character. The task is to find the longest path such that the sequence of characters along the path forms a palindrome. The path must respect graph connectivity, and characters from both ends must mirror each other.

Approach 1: Path Enumeration with Palindrome Check (Exponential Time, O(n!))

The most direct idea is to enumerate all possible simple paths in the graph using DFS or backtracking. For each path, build the string formed by node labels and check whether it is a palindrome using two pointers. This requires exploring every permutation-like path combination in dense graphs, leading to factorial growth. Time complexity is roughly O(n! * n) for path exploration and palindrome checks, with O(n) auxiliary space for recursion and path storage. This approach works only for very small graphs and mainly serves as a baseline.

Approach 2: Bitmask Dynamic Programming on Node Pairs (Optimal, O(2^n * n^2))

The key observation is that a palindrome grows symmetrically from both ends. Instead of building paths linearly, track two endpoints (u, v) that represent the current left and right ends of a potential palindromic path. Use a bitmask to record which nodes are already used. A DP state dp[mask][u][v] indicates whether a palindromic path exists that uses nodes in mask with endpoints u and v. Transitions expand the path by choosing neighbors nu of u and nv of v where the characters match. This symmetric expansion ensures the string remains a palindrome while exploring valid graph edges. The DP iterates through masks and endpoint pairs, giving time complexity O(2^n * n^2) and space complexity O(2^n * n^2). This approach combines techniques from graph traversal, dynamic programming, and bitmask state compression.

Recommended for interviews: Start by explaining brute-force path enumeration to show understanding of the search space. Then move to the symmetric DP idea where you grow the palindrome from both ends using a bitmask state. Interviewers usually expect the bitmask DP solution because it demonstrates control over graph states, state compression, and palindrome symmetry.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS Path EnumerationO(n! * n)O(n)Very small graphs or conceptual baseline for understanding the problem
Bitmask DP on Endpoint PairsO(2^n * n^2)O(2^n * n^2)General solution when node count is small enough for state compression

Video Solution

3615. Longest Palindromic Path in Graph | Weekly Contest 458 | Leetcode • Amit Choraria • 630 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Longest Palindromic Path in Graph easy or hard?
Longest Palindromic Path in Graph is classified as a hard problem because it combines graph traversal, palindrome constraints, and state-compression dynamic programming. Recognizing the symmetric endpoint expansion with bitmask DP is the main challenge.
Longest Palindromic Path in Graph Python/Java solution
Implementations usually create a DP table like dp[mask][u][v] and iterate through masks while expanding endpoints through adjacency lists. The same algorithm works across Python, Java, C++, and Go with minor syntax differences. The logic relies on bitmask iteration and neighbor traversal.
How to solve Longest Palindromic Path in Graph in O(n)?
An O(n) solution is not feasible for the general version of this problem because the algorithm must consider many combinations of nodes forming symmetric paths. The commonly accepted optimal approach is bitmask DP with O(2^n * n^2) complexity, which is manageable when the number of nodes is small.
What is the best approach for Longest Palindromic Path in Graph?
The most effective method uses bitmask dynamic programming with two endpoints. A DP state tracks a subset of visited nodes and the current pair of endpoints forming the palindrome boundaries. By expanding both ends only when characters match, the algorithm systematically builds valid palindromic paths. This reduces the search space to O(2^n * n^2).
Is Longest Palindromic Path in Graph asked at Google/Amazon/Meta?
Variants of palindromic path and state-compression graph problems appear in interviews at companies like Google and Meta. They test understanding of dynamic programming on graphs, symmetric state transitions, and bitmask optimization techniques often used for small constraint graphs.
What data structure is used in Longest Palindromic Path in Graph?
The solution typically uses adjacency lists for graph representation and a dynamic programming table indexed by bitmask and endpoint nodes. Bitmasks efficiently represent visited node subsets, while DP states track valid palindromic expansions.
What is the time complexity of Longest Palindromic Path in Graph?
The optimal solution using bitmask dynamic programming runs in O(2^n * n^2) time because each subset of nodes can be paired with two endpoints. Space complexity is also O(2^n * n^2) to store DP states. Brute force enumeration of paths can grow to O(n! * n).

Ready to solve this problem?

Practice Longest Palindromic Path in Graph with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring