Count Rotations With Exactly K Equal Adjacent Pairs solution and explanation
4 more videos on this problem
Count Rotations With Exactly K Equal Adjacent Pairs | LeetCode 4043 | Weekly Contest 518 | JavaDeveloper Coder · 17:20 · 230 views
LeetCode 4043 Count Rotations Without Generating Them 🔄 | Weekly Contest 518EdgeCaseOffByOne · 10:10 · 222 views
LeetCode Weekly Contest 518 Q1.Count Rotations With Exactly K Equal Adjacent Pairs #python #easyADevOpsEngineer · 9:06 · 160 views
LeetCode 4043: Circular adjacency — count once, price the cutAditya Mahajan · 10:52 · 51 views
LeetCode Weekly Contest 518 | 4043 & 4044 Explained in Java | First 2 ProblemsProof2Code · 17:30 · 36 views
The problem
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, soscore = 1."aba": No two adjacent characters are equal, soscore = 0."baa": The characters at positions 1 and 2 are equal, soscore = 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, soscore = 0."bcaa": The characters at positions 2 and 3 are equal, soscore = 1."caab": The characters at positions 1 and 2 are equal, soscore = 1."aabc": The characters at positions 0 and 1 are equal, soscore = 1.
Since score equals k for only 1 cyclic rotation of s, the answer is 1.
Constraints:
2 <= n == s.length <= 100sonly consists of lowercase English letters.0 <= k <= n - 1
Approach overview
Problem Overview: Given a string s and an integer k, count how many of the n cyclic rotations of s have exactly k adjacent pairs in which the two characters are equal. You can include the original string as rotation 0. The adjacency pairs are the n-1 pairs inside the linear rotated string, not the doubled circular pair.
Approach 1: Brute-Force Rotation Simulation (Brute force: O(n^2) time, O(n) space)
Generate every rotation by moving the first character to the end, or by taking s[i:] + s[:i]. For each rotation, scan the resulting string from one character to the next and count how many times s[j] == s[j+1]. Each scan costs n-1 comparisons, and there are n rotations, so the total cost is O(n^2). This is the most straightforward way to verify the answer and is acceptable when s is short, but even for n around 10^4 it becomes a poor solution.
Approach 2: Circular-Edge Sliding Window (Optimal: O(n) time, O(1) extra space)
The key is to think of the original string as a circle, not as a linear sequence. For any rotation, after the first character is the start, the linear rotated string contains n-1 of the n circular edges; the only remove is the edge from the previous start to the current start. Let’s define an equal edge i as s[i] == s[(i+1) % n]. Compute the total number of equal circular edges in one pass. Then, for a rotation starting at position i, the number of equal adjacent pairs is that the total minus the equal value of the edge that was removed. In O(n) notation, the count for rotation i is total - (s[(i-1) % n] == s[i]). This gives every rotation in a single loop, so you can precompute the total and then check each rotation in constant time. The solution is literally a sliding window over circular edges, and the string is small because no at the tree is needed for enumeration.
Recommended for interviews: The brute force shows that you understand the problem definition and can verify an answer quickly. The O(n) circular-edge approach is the one to present in a frontend code review. It shows you manage the wrap-around character by character, which avoids the O(n^2) complexity. Try to describe the boundary first and the original string, then use the formula count = total - edgeRemoved for each possible start position. That is the elegant solution that makes this an Easy problem on the site.
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:
- the adjacent pair at the front disappears, namely
s[t]ands[t + 1]; - a new adjacent pair appears at the end, namely
s[t - 1]ands[t].
All indices are taken modulo n. Thus 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:
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 ansclass 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;
}
};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;
}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
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute-Force Rotation Simulation | O(n^2) | O(n) if strings are copied | When testing small inputs or verifying the solution is trivial |
| Circular-Edge Sliding Window | O(n) | O(1) | For all cases where inputs need direct O(n) and are usually expected by interviews |
Frequently asked questions
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%.
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).