Cities | Topcoder Archive

Problem Statement

When I was a child I played a game of cities with my mom. The game goes as follows: the person who starts names a city, then another person has to name a city which starts with the letter with which the previous city ended. For example, I name a city, say Moscow, she has to name a city which starts with the letter with which my city ends, that is "W". For example, she can say Washington, then I can say Norilsk, then she can say Kiev, then I can say Vienna etc. You are not allowed to repeat a city during the game. To make my life easier my mom made her life harder. On her turn she made an extra restriction for herself: to name a city which ends with the same letter as it starts. So, our game could proceed as following: Moscow, Warsaw, Washington, Newton, Norilsk, Kursk, etc.

Your task is, given a String[] representing a dictionary of cities, return the longest number of rounds me and my mom (with her extra restriction) could have played in the game of cities using the words from this dictionary. Assume that either me or my mom can start the game.

Definition

Class:: Cities
Method:: length
Parameters:: String[]
Returns:: int
Method signature:: int length(String[] dict)
(be sure your method is public)

Constraints

dict contains between 1 and 25 elements inclusive
each element of dict has between 1 and 15 characters inclusive
each element of dict consists of letters [a-z] and [A-Z] and spaces
each element of dict can't start and can't end with a space (that is the first and the last characters of dict are letters)
elements of dict are distinct when ignoring case (that is dict can't have Moscow and moscow at the same time)

Examples

```
{"New York","Boston","Princeton","Newton"}
```
```
Returns: 3
```
We can play Boston-Newton-New York, or Princeton-Newton-New York

{"Moscow","Boston","Princeton"}

Returns: 1

{"ab","bc","cd","bb","cc","dd"}

Returns: 6

We can play ab-bb-bc-cc-cd-dd

```
{"A A","A B","A C","A D","A"}
```
```
Returns: 3
```

{"aa","ab","ac","ad","ba","bb",
"bc","bd","ca","cb","cc","cd",
"da","db","dc","dd","aba","aca","bbb",
"bcb","ccc","c","ddd","d","a"}

Returns: 25

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.