Finding the Longest Palindromic Path in a Graph

Link: https://leetcode.com/problems/longest-palindromic-path-in-graph/

📖 Interpreting the Problem

We’re given an undirected graph with n nodes, each labeled with a character. Our goal is to find the maximum possible length of a palindrome that can be formed by visiting a sequence of unique nodes along a valid path. Importantly, we may start at any node and travel to adjacent ones, but each node can only be visited once.

A palindrome reads the same forwards and backwards, so if we visit nodes in the order of labels like "aba" or "racecar", the sequence of characters must be symmetric.

For example, suppose:

• Nodes: 0, 1, 2
• Edges: [[0,1],[1,2]]
• Labels: “aba”

One valid path is 0 → 1 → 2, and the labels form the string “aba”, which is a palindrome of length 3.

🧠 First Attempts and Their Pitfalls

A natural brute-force approach would be to try all simple paths (no cycles) starting from each node, build the label strings, and check if each is a palindrome. Then return the maximum length among these.

But this quickly becomes computationally infeasible. The number of simple paths in a graph grows exponentially with the number of nodes. For instance, with n = 14, there are potentially 14! simple paths. For each such path, building the label string takes O(N), and checking if it forms a palindrome also takes O(N). This means a brute-force solution has factorial time complexity and is impossible to run within time limits for even moderately sized graphs.

Additionally, storing all visited node combinations using a boolean array would be very memory inefficient, and we wouldn’t be able to leverage efficient hashing or DP memoization unless we used a more compact representation.

You might also think of using DFS with backtracking to explore paths and cache palindromic results. However, checking palindromes repeatedly and maintaining state would still take O(2<sup>N</sup> * N) time, which is too slow.

💡 The Breakthrough Insight

Rather than trying to generate all paths and check for palindromes, we flip the strategy: what if we work from the outside in, pairing nodes with matching labels and checking if they can be the ends of a palindrome?

If we fix two nodes head and tail that have the same label, we can ask: is there a path from head to tail such that we can wrap a palindrome around it? If so, we recursively look for matching pairs of neighbors from head and tail, growing the palindrome inward.

This structure is ideal for dynamic programming with memoization. We define a state (head, tail, visited_nodes) and compute the maximum palindromic length that can be built with these boundary nodes and visited set

Another key optimization is to only try pairs of nodes that have the same label—no palindrome can form from mismatched ends. We pre-group nodes by label to iterate only over relevant pairs.

🔍 Walking Through the Algorithm (with Full-Length Example)

Let’s walk through a case:

• n = 4, edges = [[0,1], [1,2], [1,3]], label = “abba”

The graph:

    0
    |
    1
   / \
  2   3

We pair nodes with the same label: nodes 0 & 3 (both ‘a’), and nodes 1 & 2 (both ‘b’).

• Try (0,3): Are they connected via a symmetric structure with matching inner labels?
• We recursively try to pair neighbors of 0 and 3: (1,1). Since this is the same node, it adds 1 to the palindrome.
• The full path is 0 → 1 → 3, labels = “aba”

We track visited nodes with bitmasks and use memoization to prevent recomputation.

🖼️ Suggested Diagram
Draw the recursive tree of calls with (head, tail, visited) states. Show how nodes with the same label are connected via inner symmetric paths.

🗾️ Pseudocode

initialize graph and label groups
initialize memoization table dp
for each label:
    for each pair of nodes with that label:
        run recursive function func(head, tail, visited)
        update max length
return max length

function func(head, tail, visited):
    if head == tail:
        return 1
    if result for (head, tail, visited) is already in dp:
        return dp result

    max_length = 0
    for each neighbor hc of head:
        if hc is already visited:
            continue
        for each neighbor tc of tail:
            if tc is already visited:
                continue
            if labels of hc and tc do not match:
                continue
            result = func(hc, tc, visited | hc | tc)
            if result > 0:
                max_length = max(max_length, result)

    if max_length == 0 and head and tail are not directly connected:
        return 0
    return max_length + 2

💻 Source Code

class Solution {
public:
    unordered_map<char, vector<int>> labelMap; // Group nodes by label
    unordered_map<int, vector<int>> G;         // Adjacency list for graph
    bool connected[14][14];                    // Direct connection check
    int dp[14][14][1 << 14];                   // Memoization table

    // Recursive DP: can we build a palindrome from head to tail with current visited state?
    int func(int head, int tail, int state, string &label) {
        if (head == tail) return 1; // Odd-length palindrome center
        if (dp[head][tail][state] != -1) return dp[head][tail][state];

        int ans = 0;
        for (auto &hc : G[head]) {            // Try next for head
            if (state & (1 << hc)) continue; // Skip visited
            for (auto &tc : G[tail]) {        // Try next for tail
                if (state & (1 << tc)) continue;
                if (label[hc] != label[tc]) continue; // Must match
                int childCan = func(hc, tc, state | (1 << hc) | (1 << tc), label);
                if (childCan > 0) {
                    ans = max(ans, childCan);
                }
            }
        }

        // If no valid inward match and not directly connected, return 0
        if (ans == 0 && !connected[head][tail]) return dp[head][tail][state] = 0;
        return dp[head][tail][state] = ans + 2; // Include current head-tail pair
    }

    int maxLen(int n, vector<vector<int>>& edges, string label) {
        memset(connected, false, sizeof(connected));
        for (auto &edge : edges) {
            int u = edge[0], v = edge[1];
            G[u].push_back(v);
            G[v].push_back(u);
            connected[u][v] = connected[v][u] = true;
        }

        for (int i = 0; i < n; ++i) {
            labelMap[label[i]].push_back(i);
        }

        memset(dp, -1, sizeof(dp));
        int ans = 1;

        for (auto &[ch, nodes] : labelMap) {
            for (int i = 0; i < nodes.size(); ++i) {
                for (int j = i + 1; j < nodes.size(); ++j) {
                    ans = max(ans, func(nodes[i], nodes[j], (1 << nodes[i]) | (1 << nodes[j]), label));
                }
            }
        }

        return ans;
    }
};

📌 Summary and Key Takeaways

The trick to solving this problem efficiently was recognizing the symmetry inherent in palindromes and flipping the brute-force strategy. By working from outer matching pairs inward and using bitmask DP, we made the exponential space of simple paths tractable.

This problem is an excellent demonstration of the following topics.

• Bitmasking for subset state management
• Dynamic programming over graphs
• Recursive symmetry exploitation