ThreeSameLetters | Topcoder Archive

Problem Statement

A string is called a block if it consists of exactly three equal letters.

A string is called a one-block string if it contains exactly one contiguous substring that is a block.

For example:

"aaa" and "abcccdd" are one-block strings
"noblocks" and "ababab" are not one-block strings, as they do not contain any blocks
"xxxyyyzzz" and "baaaad" are not one-block strings, as each of them contains at least two blocks

Note that the two blocks in "baaaad" overlap partially.

You are given the ints L and S. If we can only use the first S lowercase letters of the English alphabet, how many different one-block strings of length L are there? Return their count modulo 10^9 + 7.

Definition

Class:: ThreeSameLetters
Method:: countStrings
Parameters:: int, int
Returns:: int
Method signature:: int countStrings(int L, int S)
(be sure your method is public)

Constraints

L will be between 1 and 26, inclusive.
S will be between 1 and 26, inclusive.

Examples

```
3
```
```
7
```
```
Returns: 7
```
The seven one-block strings are "aaa", "bbb", "ccc", ..., "ggg".
```
4
```
```
2
```
```
Returns: 4
```
The four one-block strings are "aaab", "abbb", "baaa", and "bbba".
```
2
```
```
17
```
```
Returns: 0
```
```
10
```
```
11
```
```
Returns: 410199993
```
Don't forget to do the calculations modulo 10^9 + 7.

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.