Count Rotations With Exactly K Equal Adjacent Pairs - Solution & Explanation

Easy8 min read

Problem Statement

You are given a string s of length n and an integer k.

A cyclic rotation of s is obtained by choosing a prefix of s whose length is between 0 and n - 1 (inclusive), and moving it to the end of the string while preserving the order of all characters.

For every cyclic rotation of s, let its score be the number of indices i such that 0 <= i < n - 1 and the characters at positions i and i + 1 are equal.

Return the number of cyclic rotations of s whose score equals k.

Example 1:

Input: s = "aab", k = 1

Output: 2

Explanation:

The cyclic rotations of s are:

"aab": The characters at positions 0 and 1 are equal, so score = 1.
"aba": No two adjacent characters are equal, so score = 0.
"baa": The characters at positions 1 and 2 are equal, so score = 1.

Since score equals k for 2 cyclic rotations of s, the answer is 2.

Example 2:

Input: s = "abca", k = 0

Output: 1

Explanation:

The cyclic rotations of s are:

"abca": No two adjacent characters are equal, so score = 0.
"bcaa": The characters at positions 2 and 3 are equal, so score = 1.
"caab": The characters at positions 1 and 2 are equal, so score = 1.
"aabc": The characters at positions 0 and 1 are equal, so score = 1.

Since score equals k for only 1 cyclic rotation of s, the answer is 1.

Constraints:

2 <= n == s.length <= 100
s only consists of lowercase English letters.
0 <= k <= n - 1

Solution

Let n be the length of the string. First compute the score of the original string s, i.e. the number of indices i such that s[i] = s[i + 1] (0 leq i < n - 1). If score = k, increment the answer by 1.

Then start from the original string and cyclically shift it left by one character, n - 1 times in total. On the t-th shift (t = 0, 1, ldots, n - 2), the character moved to the end is s[t], and the score changes in only two places: