Welcome to Subscribe On Youtube

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

Thinking

A cyclic left shift changes only the adjacent pairs at the two ends; equalities in the middle stay. Rebuilding the string for every rotation would be quadratic.

Compute the score of the original string, then in $O(1)$ subtract the lost head pair and add the new tail pair, counting how often the score equals $k$.

Indices modulo $n$ let all $n$ rotations run on the original string.

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$.

  • 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;
    }
}

  • 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;
    }
};

  • 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


  • 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
}


  • 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;
}

All Problems

All Solutions