PalindromePath | Topcoder Archive

Problem Statement

You are given an undirected graph with n nodes, labeled 0 through n-1. You are given the description of its edges in int[]s a and b and in the String c. For each valid i, the vertices a[i] and b[i] are connected by an edge, and the character c[i] is the label of that edge.

A walk in the graph is any sequence of consecutive edges. (In other words, a walk is a path that may visit the same vertex and also use the same edge multiple times.) The length of a walk is the number of edges it contains. The label of a walk is the concatenation of labels of edges it contains, in order.

A palindrome is a string that reads the same forwards and backwards. Some palindromes: "a", "abba", "racecar", "steponnopets".

We are interested in walks that go from node 0 to node 1 and have a palindromic label. Return the length of the shortest such walk. If there is no such walk, return -1 instead.

Definition

Class:: PalindromePath
Method:: shortestLength
Parameters:: int, int[], int[], String
Returns:: int
Method signature:: int shortestLength(int n, int[] a, int[] b, String c)
(be sure your method is public)

Constraints

n will be between 2 and 20, inclusive.
a will contain between 1 and n*(n-1)/2 elements, inclusive.
a, b and c will contain the same number of elements.
Each element in a will be between 0 and n-1, inclusive.
Each element in b will be between 0 and n-1, inclusive.
Each character in c will be a lowercase English letter ('a'-'z').
For each valid i, a[i] != b[i].
If i!=j then {a[i], b[i]} != {a[j], b[j]}.

Examples

```
5
```
```
{2,2,0,3,4}
```
```
{0,1,3,4,1}
```
```
"abxyx"
```
```
Returns: 3
```
The shortest walk between 0 and 1 is 0-2-1. However, the label of this walk is "ab" which is not a palindrome. The shortest walk that has a palindromic label is 0-3-4-1.

{2,2,0,3,4}

{0,1,3,4,1}

"abxyz"

Returns: -1

This time there is no such path.

```
7
```
```
{0,0,3,4,5,6}
```
```
{2,3,4,5,6,1}
```
```
"abaaaa"
```
```
Returns: 9
```
Note that sometimes you need to use an edge more than once: the optimal solution is 0-2-0-2-0-3-4-5-6-1.

{0,0,3,4,5}

{2,3,4,5,1}

"abaaa"

Returns: -1

```
2
```
```
{0}
```
```
{1}
```
```
"x"
```
```
Returns: 1
```
```
20
```
```
{18}
```
```
{19}
```
```
"z"
```
```
Returns: -1
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.