OrderedSuperString | Topcoder Archive

Problem Statement

A string X is an ordered superstring of the String[] words if

Each element of words is a substring of X.
There exists a sequence of indices x_1 <= x_2 <= ... <= x_n, where n is the number of elements in words. For each element k of words, where k is a 1-based index, there is an occurrence of words[k] that starts at the x_k-th letter of X.

For example "abca" is an ordered superstring of {"abc", "ca"}, but "cabc" is not.

Given a String[] words, return the length of its shortest ordered superstring.

Definition

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

Constraints

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

Examples

```
{"abc","ca"}
```
```
Returns: 4
```
This is the example from the problem statement. The shortest ordered superstring is "abca". The sequence of indices is {0, 2}. There is an occurrence of "abc" starting at character 0 of "abca", and there is an occurrence of "ca" starting at character 2 of "abca".
```
{"a","a","b","a"}
```
```
Returns: 3
```
Although the given words are all substrings of "ab", they do not appear in the proper order. The shortest ordered superstring is "aba".

{"abcdef", "ab","bc", "de","ef"}

Returns: 6

{"ab","bc", "de","ef","abcdef"}

Returns: 12

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.