SimilarPairs | Topcoder Archive

Problem Statement

You are given a String[] text. Concatenate all the elements to make one string. A pair of non-empty two non-overlapping substrings of equal length (A, B) is called k-similar if there are no more than k positions where A and B have different characters. Return the number of distinct strings that belong to at least one such pair.

Definition

Class:: SimilarPairs
Method:: howManyElements
Parameters:: String[], int
Returns:: int
Method signature:: int howManyElements(String[] text, int k)
(be sure your method is public)

Constraints

text will contain between 1 and 50 elements, inclusive.
Each element of text will contain between 1 and 50 characters, inclusive.
Each element of text will contain only lowercase letters ('a'..'z').
k will be between 0 and 2500, inclusive.

Examples

```
{"abacd"}
```
```
1
```
```
Returns: 6
```
The following strings each belong to at least one similar pair: "a", "b", "c", "d", "ab", "ac".
```
{"aaaa"}
```
```
0
```
```
Returns: 2
```
```
{"abcdefgh"}
```
```
2
```
```
Returns: 15
```
```
{"a", "ab", "abc"}
```
```
0
```
```
Returns: 3
```
```
{"abacd"}
```
```
0
```
```
Returns: 1
```

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.