AllInclusiveString | Topcoder Archive

Problem Statement

This problem has an unusual time limit: 5 seconds.

You are given the String[] a. Each element of a consists of exactly two letters. All letters that may appear in a are 'a' to 'p', inclusive.

We call a string S all-inclusive if it contains every string from a as a (not necessarily contiguous) subsequence.

For example, if a={"ab","cd"}, then strings "abcd", "acbd" and "babcde" are all-inclusive, but strings "bacd" and "abab" are not.

Let L be the length of the shortest all-inclusive string, and C the number of all-inclusive strings of length exactly L. Return a int[] with two integers: L and (C modulo 998,244,353).

Definition

Class:: AllInclusiveString
Method:: shortest
Parameters:: String[]
Returns:: int[]
Method signature:: int[] shortest(String[] a)
(be sure your method is public)

Notes

Constraints

a contains between 0 and 256 elements, inclusive.
Each element of a is a string of length 2, consisting of characters 'a' to 'p'.
All elements of a are distinct

Examples

```
{"aa", "ac"}
```
```
Returns: {3, 2 }
```
There are exactly two all-inclusive strings of length 3, "aac" and "aca". There are no shorter all-inclusive strings.
```
{}
```
```
Returns: {0, 1 }
```
An empty string is all-inclusive.
```
{"aa", "bb", "cc"}
```
```
Returns: {6, 90 }
```
An all-inclusive string of length 6 contains 2 of each characters 'a', 'b' and 'c' in any order, the answer is thus 6!/2!2!2!.

{"ac","ag","aj","bb","bf","bg","bh","ce","cg","da","de","df","dg","di","ea","eb","ef","ei","fb","fc","fg","gc","gf","gi","gj","hb","hh","hi","ib","ih","ij","jj"}

Returns: {15, 11461680 }

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.