Skip to content

3615. Longest Palindromic Path in Graph

SourceWeekly Contest 458 Q4DifficultyHardRating2463

Description

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.

Solutions

Solution 1

Thinking

We want a simple path whose vertex labels form a palindrome. \(n\) is small, so the used-vertex set can be a bitmask.

A palindrome grows from both ends: when the current ends share a label, each end steps to an unused neighbor with that same label. Odd and even palindromes start from a single vertex or a pair of adjacent equal labels.

Let \(f[S][i][j]\) mean a palindromic path on vertex set \(S\) with ends \(i,j\). Transition through unused neighbors of \(i\) and \(j\) that carry equal labels. The answer is the largest \(|S|\) among reachable states.

1


1


1


1

Comments