LongestSubanagramChain | Topcoder Archive

Problem Statement

A word A is called an anagram of a word B if it is possible to change the order of letters in A to get the word B. For example, "coder" is an anagram of "decor".

A word A is called a subword of a word B if A can be obtained from B by removing some letters (possibly 0) from the beginning of B, and removing some letters (possibly 0) from the end of B. For example, "coder" is a subword of "decoder".

A word A is called a subanagram of a word B if there is a word C such that C is an anagram of B and A is a subword of C. For example, "coder" is a subanagram of "record" because the word "coderr" is an anagram of "record" and contains "coder" as a subword.

Let words A and B have the same number of characters. We say that word A dominates word B if for all i, the i-th letter of A is equal to the i-th letter of B or comes after it alphabetically. For example, the word "coder" dominates the word "amber", but doesn't dominate the word "after" (because the 3-rd letter of "coder" is "d" which comes alphabetically before "t" - the 3-rd letter of "after").

A sequence of words A0, A1, ..., An-1 of equal length is called a chain if, for all i from 1 to n-1, word A_i dominates word A_i-1.

You are given a String[] B. Return the maximal value of k where there exists a chain A₀, A₁, ..., A_n-1 such that all words in the chain have length k, and for all i, word A_i is a subanagram of word B[i].

Definition

Class:: LongestSubanagramChain
Method:: getLength
Parameters:: String[]
Returns:: int
Method signature:: int getLength(String[] B)
(be sure your method is public)

Constraints

B will contain between 1 and 50 elements, inclusive.
Each element of B will contain between 1 and 50 characters, inclusive.
Each element of B will contain only lowercase letters ('a'-'z').

Examples

```
{"abaa", "abab", "aaba", "babb"}
```
```
Returns: 3
```
In this example the required chain is, for example, "aaa", "aba", "aba", "bbb".
```
{"aa", "bbb", "ccc", "ddd", "eee"}
```
```
Returns: 2
```
Note that elements of B can have different length.

{"coder", "coding", "topcoder", "program"}

Returns: 4

```
{"b", "a"}
```
```
Returns: 0
```

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.