Skip to content

4043. Count Rotations With Exactly K Equal Adjacent Pairs

Description

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

Solutions

Solution 1: Simulation

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 \(\textit{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:

  • the adjacent pair at the front disappears, namely \(s[t]\) and \(s[t + 1]\);
  • a new adjacent pair appears at the end, namely \(s[t - 1]\) and \(s[t]\).

All indices are taken modulo \(n\). Thus \(\textit{score}\) can be updated in \(O(1)\) time, and we count the cyclic rotations whose score equals \(k\).

The time complexity is \(O(n)\) and the space complexity is \(O(1)\), where \(n\) is the length of the string \(s\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def countRotations(self, s: str, k: int) -> int:
        n = len(s)
        score = sum(a == b for a, b in pairwise(s))
        ans = int(score == k)

        for i in range(n, n * 2 - 1):
            score += int(s[i % n] == s[(i - 1) % n])
            score -= int(s[i % n] == s[(i + 1) % n])
            ans += int(score == k)

        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int countRotations(String s, int k) {
        int n = s.length();
        int score = 0;

        for (int i = 0; i < n - 1; i++) {
            score += s.charAt(i) == s.charAt(i + 1) ? 1 : 0;
        }

        int ans = score == k ? 1 : 0;

        for (int i = n; i < n * 2 - 1; i++) {
            score += s.charAt(i % n) == s.charAt((i - 1) % n) ? 1 : 0;
            score -= s.charAt(i % n) == s.charAt((i + 1) % n) ? 1 : 0;
            ans += score == k ? 1 : 0;
        }

        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int countRotations(string s, int k) {
        int n = s.size();
        int score = 0;

        for (int i = 0; i < n - 1; i++) {
            score += s[i] == s[i + 1];
        }

        int ans = score == k;

        for (int i = n; i < n * 2 - 1; i++) {
            score += s[i % n] == s[(i - 1) % n];
            score -= s[i % n] == s[(i + 1) % n];
            ans += score == k;
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func countRotations(s string, k int) int {
    n := len(s)
    score := 0

    for i := 0; i < n-1; i++ {
        if s[i] == s[i+1] {
            score++
        }
    }

    ans := 0
    if score == k {
        ans++
    }

    for i := n; i < n*2-1; i++ {
        if s[i%n] == s[(i-1)%n] {
            score++
        }
        if s[i%n] == s[(i+1)%n] {
            score--
        }
        if score == k {
            ans++
        }
    }

    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function countRotations(s: string, k: number): number {
    const n = s.length;
    let score = 0;

    for (let i = 0; i < n - 1; i++) {
        score += s[i] === s[i + 1] ? 1 : 0;
    }

    let ans = score === k ? 1 : 0;

    for (let i = n; i < n * 2 - 1; i++) {
        score += s[i % n] === s[(i - 1) % n] ? 1 : 0;
        score -= s[i % n] === s[(i + 1) % n] ? 1 : 0;
        ans += score === k ? 1 : 0;
    }

    return ans;
}

Comments