Count Rotations With Exactly K Equal Adjacent Pairs Python/Java solution

In Python, compute total = sum(s[i] == s[(i + 1) % len(s)] for i in range(n)), then loop i from 0 to n-1. If total - (s[(i - 1) % n] == s[i]) == k, increment ans. The solution is the same for Java; you can use local variables and modular arithmetic with no extra data structures.

How to solve Count Rotations With Exactly K Equal Adjacent Pairs in O(n)?

First, compute total = total count of i such that s[i] == s[(i + 1) % n]. Then for each rotation starting at i, compute count = total - (s[(i - 1) % n] == s[i]). If count equals k, increment the answer. This is O(n) for just a way to solve the problem effectively.

What is the best approach for Count Rotations With Exactly K Equal Adjacent Pairs?

The O(n) circular-edge sliding window is the best approach. It computes the total number of equal circular edges in a single pass, then uses a special case for each rotation to subtract the one edge that is not in the adjacent. This gives O(n) time and O(1) extra space.

Is Count Rotations With Exactly K Equal Adjacent Pairs asked at Google/Amazon/Meta?

There is no conclusive public tag for any of the three major companies for this exact problem. The problem is useful because it tests the concept of shared cyclic edges and sliding windows from a string, which is primarily used in earlier rounds of technical interviews.

What data structure is used in Count Rotations With Exactly K Equal Adjacent Pairs?

No heavy data structure is needed. You need the string array of the input and a numeric variable to compute equal adjacent pairs. The exact algorithm is a sliding-window and around loop, not necessarily a custom map or a stack.

What is the time complexity of Count Rotations With Exactly K Equal Adjacent Pairs?

The optimal time complexity is O(n), where n is the length of the string. You only need to inspect each character once more continuous string, once to compute the total equal circular edges and once to enumerate the rotation. Brute force is O(n^2).

Description Hints 3 Solution Video 17:20

4043. Count Rotations With Exactly K Equal Adjacent Pairs

Q: Is Count Rotations With Exactly K Equal Adjacent Pairs easy or hard?

The problem is classified as Easy. The brute force is straightforward and might be a simple while loop. The transition from the edge cases is the sorted(n) but can be solved by making an O(log) while remaining, but it is common for nudge. This explains its high acceptance rate should be about 71%.

Easy72.3% acceptance

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

Topics

Hints open one at a time

Hint 1

1a (Simulation). Construct the rotation for each possible prefix length and count its equal adjacent pairs.

Hint 2

2a (Counting). Let total be the number of equal adjacent pairs when the string is treated as circular, including the pair formed by its last and first characters.

Hint 3

2b (Counting). Each rotation excludes exactly one circular adjacent pair. Its score is total - 1 if the excluded pair has equal characters, and total otherwise.

17:20

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def countRotations(self, s: str, k: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"aab"
1

Input

"abca"
0

Your code is saved on this device.Solution