AlphabetOrderDiv2 | Topcoder Archive

Problem Statement

The ancient civilization of Nlogonia used the same 26 letters as modern English: 'a'-'z'. However, we do not know the order in which these letters appeared in the Nlogonian alphabet.
One particular custom in Nlogonia was that in a good word the letters appear in non-decreasing order. For example, in English the word "ciel" is not a good word because in the alphabet 'i' is after 'e'. The word "ceil" is a good word because 'c' <= 'e' <= 'i' <= 'l'.
You are given the String[] words. Each element of words is a nonempty string of lowercase English letters. Return "Possible" if it is possible that all elements of words were good words in Nlogonian, and "Impossible" otherwise.
In other words, return "Possible" if and only if there is at least one possible Nlogonian alphabet such that the letters of each word in words are in non-decreasing alphabetical order.

Definition

Class:: AlphabetOrderDiv2
Method:: isOrdered
Parameters:: String[]
Returns:: String
Method signature:: String isOrdered(String[] words)
(be sure your method is public)

Constraints

words has between 2 and 100 elements inclusive.
The size of each element of words will be between 1 and 100 inclusive.
Elements of words contains only English lowercase letters from 'a' to 'z'.

Examples

```
{"single","round","match"}
```
```
Returns: "Possible"
```
One possible Nlogonian alphabet is "bfjkmapqrositchundglevwxyz".
```
{"topcoder","topcoder"}
```
```
Returns: "Impossible"
```
The word "topcoder" can never be a good word. The character 'o' cannot be both before 'p' and after 'p' in the alphabet.

{"algorithm", "contest"}

Returns: "Impossible"

```
{"pink","floyd"}
```
```
Returns: "Possible"
```

{"gimnasia","y","esgrima","la","plata"}

Returns: "Impossible"

```
{"hello","hello"}
```
```
Returns: "Possible"
```
This is a good word for any alphabet in which the letters 'h', 'e', 'l', and 'o' appear in this order.

{"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}

Returns: "Possible"

In this case the English alphabet is one of the valid permutations.

```
{"abc","bca"}
```
```
Returns: "Impossible"
```
'a' must come before 'c' (because of the first name) and after 'c' (because of the second name) and that is a contradiction. Thus, there is no valid solution.

{"aaaaa","eeeee","iiiii","ooooo","uuuuu"}

Returns: "Possible"

Any order is valid in this case

```
{"ab","bc","ca"}
```
```
Returns: "Impossible"
```

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.