FastPrep
Problem · Dynamic Programming

Strings With No k Consecutive Identical Characters

● MediumSalesforceOA
See Salesforce hiring insights

You are given two integers:

  • n: length of string
  • k: maximum allowed consecutive identical characters

A string is invalid if it contains k or more consecutive identical characters.

Return the total number of strings of length n formed using lowercase English letters such that no character appears k or more times consecutively.

Return the answer modulo 10^9 + 7.

Examples
01 · Example 1
n = 3
k = 2
return = 16250

Total strings of length 3 is 26^3 = 17576.

Invalid strings are those with at least one adjacent equal pair. For this case, the valid count is 16250.

Constraints
  • 1 <= n <= 10^5
  • 1 <= k < n
More Salesforce problems
drafts saved locally
public int stringsWithNoKConsecutiveIdenticalCharacters(int n, int k) {
  // write your code here
}
n3
k2
expected16250
sign in to submit