KDoubleSubstrings | Topcoder Archive

Problem Statement

A k-double string is a non-empty string consisting of two equal length halves, where the first half differs from the second half at no more than k positions. For example, "contestcontest", "oopoop" and "aa" are 0-double strings. "contestkontest" is a 1-double string, and "poorpork", "artbat", and "yesyep" are 2-double strings. Obviously, all 0-double strings are also 1-double strings, all 1-double strings are also 2-double strings, etc.

You will be given a String[] str and an int k. Concatenate the elements of str to form one long string, and return the number of k-double substrings contained in that string.

If the same string exists in several different positions, count it as many times as it exists. Also, k-double substrings can overlap. See the examples for more details.

Definition

Class:: KDoubleSubstrings
Method:: howMuch
Parameters:: String[], int
Returns:: int
Method signature:: int howMuch(String[] str, int k)
(be sure your method is public)

Constraints

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

Examples

```
{"aa"}
```
```
0
```
```
Returns: 1
```
"aa" is the only 0-double substring.
```
{"aaaa"}
```
```
0
```
```
Returns: 4
```
There are four substrings of even length and all of them are 0-double strings.
```
{"contest", "kontest"}
```
```
1
```
```
Returns: 14
```
Each pair of consecutive letters form a 1-double substring and the whole string form one more 1-double substring.
```
{"abacaba", "d", "abacaba"}
```
```
1
```
```
Returns: 34
```
```
{"areyouready"}
```
```
2
```
```
Returns: 18
```

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.