3615. Longest Palindromic Path in Graph Hard

1/**
2 * [3615] Longest Palindromic Path in Graph
3 *
4 * 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.
5 * You are also given a string label of length n, where label[i] is the character associated with node i.
6 * You may start at any node and move to any adjacent node, visiting each node at most once.
7 * Return the maximum possible length of a <span data-keyword="palindrome-string">palindrome</span> that can be formed by visiting a set of unique nodes along a valid path.
8 *  
9 * <strong class="example">Example 1:
10 * <div class="example-block">
11 * Input: <span class="example-io">n = 3, edges = [[0,1],[1,2]], label = "aba"</span>
12 * Output: <span class="example-io">3</span>
13 * Explanation:
14 * <img src="https://assets.leetcode.com/uploads/2025/06/13/screenshot-2025-06-13-at-230714.png" style="width: 250px; height: 85px;" />
15 * 
16 * 	The longest palindromic path is from node 0 to node 2 via node 1, following the path 0 &rarr; 1 &rarr; 2 forming string "aba".
17 * 	This is a valid palindrome of length 3.
18 * </div>
19 * <strong class="example">Example 2:
20 * <div class="example-block">
21 * Input: <span class="example-io">n = 3, edges = [[0,1],[0,2]], label = "abc"</span>
22 * Output: <span class="example-io">1</span>
23 * Explanation:
24 * <img src="https://assets.leetcode.com/uploads/2025/06/13/screenshot-2025-06-13-at-230017.png" style="width: 200px; height: 150px;" />
25 * 
26 * 	No path with more than one node forms a palindrome.
27 * 	The best option is any single node, giving a palindrome of length 1.
28 * </div>
29 * <strong class="example">Example 3:
30 * <div class="example-block">
31 * Input: <span class="example-io">n = 4, edges = [[0,2],[0,3],[3,1]], label = "bbac"</span>
32 * Output: <span class="example-io">3</span>
33 * Explanation:
34 * <img src="https://assets.leetcode.com/uploads/2025/06/13/screenshot-2025-06-13-at-230508.png" style="width: 200px; height: 200px;" />
35 * 
36 * 	The longest palindromic path is from node 0 to node 1, following the path 0 &rarr; 3 &rarr; 1, forming string "bcb".
37 * 	This is a valid palindrome of length 3.
38 * </div>
39 *  
40 * Constraints:
41 * 
42 * 	1 <= n <= 14
43 * 	n - 1 <= edges.length <= n * (n - 1) / 2
44 * 	edges[i] == [ui, vi]
45 * 	0 <= ui, vi <= n - 1
46 * 	ui != vi
47 * 	label.length == n
48 * 	label consists of lowercase English letters.
49 * 	There are no duplicate edges.
50 * 
51 */
52pub struct Solution {}
53
54// problem: https://leetcode.com/problems/longest-palindromic-path-in-graph/
55// discuss: https://leetcode.com/problems/longest-palindromic-path-in-graph/discuss/?currentPage=1&orderBy=most_votes&query=
56
57// submission codes start here
58
59impl Solution {
60    pub fn max_len(n: i32, edges: Vec<Vec<i32>>, label: String) -> i32 {
61        0
62    }
63}
64
65// submission codes end
66
67#[cfg(test)]
68mod tests {
69    use super::*;
70
71    #[test]
72    fn test_3615() {
73    }
74}
75