CompletelyDifferentStrings | Topcoder Archive

Problem Statement

You are given an int S and a String[] forbidden. The strings in forbidden only use the first S lowercase English letters, and all these strings have the same length L.

Two strings of length L are called completely different if they differ at every index. For example, X="abcd" and Y="bcda" are completely different but X="frog" and Y="plow" are not because X[2] = Y[2] = 'o'.

Compute and return the total number of strings with the following properties:

The length of the string is L. (That is, its length is the same as the length of the strings in forbidden.)
Each character of the string is one of the first S lowercase English letters.
The string is completely different from every string in forbidden.

Definition

Class:: CompletelyDifferentStrings
Method:: count
Parameters:: int, String[]
Returns:: int
Method signature:: int count(int S, String[] forbidden)
(be sure your method is public)

Constraints

S will be between 1 and 26, inclusive.
forbidden will contain between 1 and 30 elements, inclusive.
All elements of forbidden will have the same length L.
L will be between 1 and 6, inclusive.
Each character in each element of forbidden will be one of the first S lowercase English letters.

Examples

```
3
```
```
{"ab"}
```
```
Returns: 4
```
As S = 3, we are only using the first three lowercase English letters: 'a', 'b', and 'c'. We are looking for strings of length 2 that are completely different from "ab". There are four such strings: "ba", "bc", "ca", and "cc".
```
1
```
```
{"aaaaa", "aaaaa"}
```
```
Returns: 0
```
The only string of length 5 is "aaaaa", but this string is not completely different from the (identical) forbidden string "aaaaa". Thus, there are no strings with all the properties we need.

{"baba", "babe", "cage", "cafe", "feed", "deed", "deaf", "dead"}

Returns: 90

```
3
```
```
{"abacaa", "abacaa", "acabab"}
```
```
Returns: 8
```
Note that the strings in forbidden are not necessarily distinct.

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.