Connection Status:
Competition Arena > ThreeSameLetters

ThreeSameLetters

TCO18 Fun 1B · 2018-04-20 · by misof

TCO18 Fun 1B · 2018-04-20 · by misof · Dynamic Programming
Class Name: ThreeSameLetters
Return Type: int
Method Name: countStrings
Arg Types: (int, int)
Problem Statement

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.

Constraints

  • L will be between 1 and 26, inclusive.
  • S will be between 1 and 26, inclusive.
Examples
0)
3
7
Returns: 7

The seven one-block strings are "aaa", "bbb", "ccc", ..., "ggg".

1)
4
2
Returns: 4

The four one-block strings are "aaab", "abbb", "baaa", and "bbba".

2)
2
17
Returns: 0
3)
10
11
Returns: 410199993

Don't forget to do the calculations modulo 10^9 + 7.

4)
26
26
Returns: 450838424

Submissions are judged against all 106 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ThreeSameLetters with a public method int countStrings(int L, int S) · 106 test cases · 2 s / 256 MB per case

Submitting as anonymous