Longest palindromic path in graph

String Dynamic Programming Bit Manipulation Graph Theory Bitmask

22.0% acceptance

Feb 25, 2026

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.

Solution

Rust

Time O(n * m)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_len(n: i32, edges: Vec<Vec<i32>>, label: String) -> i32 {
    let n = n as usize;
    let lb: Vec<usize> = label.chars().map(|c| c as usize - 'a' as usize).collect();
    let total = 1usize << n;
    let all = (total - 1) as u32;

    // adj[u]: bitmask of neighbours of u
    let mut adj = vec![0u32; n];
    for e in &edges {
      let (u, v) = (e[0] as usize, e[1] as usize);
      adj[u] |= 1 << v;
      adj[v] |= 1 << u;
    }

    // dp[mask][u] = bitmask of nodes v such that there is a palindromic
    // path from u to v whose node-set is exactly `mask`.
    // Build palindromes inside-out: seed single nodes and 2-node edges,
    // then wrap each existing palindrome with a matching pair (l', r').
    let mut dp = vec![[0u16; 14]; total];

    let mut best = 1i32;

    // Seed: single-node palindromes
    for u in 0..n {
      dp[1 << u][u] |= 1 << u;
    }

    // Seed: 2-node palindromes (edge u-v with same label)
    for u in 0..n {
      let mut nbrs = adj[u];
      while nbrs != 0 {
        let v = nbrs.trailing_zeros() as usize;
        nbrs &= nbrs - 1;
        if u < v && lb[u] == lb[v] {
          let m = (1 << u) | (1 << v);
          dp[m][u] |= 1 << v;
          dp[m][v] |= 1 << u;
          best = best.max(2);
        }
      }
    }

    // Expand existing palindromes by wrapping with a new matching outer pair
    for mask in 1..total {
      for u in 0..n {
        if dp[mask][u] == 0 { continue; }
        let pc = mask.count_ones() as i32;
        best = best.max(pc);
        // Candidates for new outer nodes: not in mask, adjacent to u (left end)
        let avail = all & !(mask as u32);
        let mut lc = adj[u] & avail;
        while lc != 0 {
          let lp = lc.trailing_zeros() as usize;
          lc &= lc - 1;
          let mut vs = dp[mask][u];
          while vs != 0 {
            let v = vs.trailing_zeros() as usize;
            vs &= vs - 1;
            // Candidates adjacent to v (right end), not mask, not lp
            let mut rc = adj[v] & avail & !(1 << lp);
            while rc != 0 {
              let rp = rc.trailing_zeros() as usize;
              rc &= rc - 1;
              if lb[lp] == lb[rp] {
                let nm = mask | (1 << lp) | (1 << rp);
                dp[nm][lp] |= 1 << rp;
                dp[nm][rp] |= 1 << lp;
                best = best.max(pc + 2);
              }
            }
          }
        }
      }
    }

    best
  }
}