4043. 恰好有 K 对相等相邻字符的循环移位数量

题目描述

给你一个长度为 n 的字符串 s 和一个整数 k。

s 的一次 循环移位 可以通过以下方式得到：选择 s 的一个长度在 0 到 n - 1（包含两端）之间的前缀，并将其移动到字符串末尾，同时保持所有字符的相对顺序不变。

对于 s 的 每一种 循环移位，定义其得分为满足以下条件的下标 i 的数量：0 <= i < n - 1，且位置 i 和 i + 1 处的字符相同。

返回得分等于 k 的循环移位数量。

字符串的前缀是指从字符串开头开始，并延伸到字符串中某个位置的子串。

子串是字符串中一段连续的字符序列，可以为空。

示例 1：

输入： s = "aab", k = 1

输出： 2

解释：

s 的所有循环移位为：

"aab"：位置 0 和 1 处的字符相同，因此 score = 1。
"aba"：不存在两个相邻且相同的字符，因此 score = 0。
"baa"：位置 1 和 2 处的字符相同，因此 score = 1。

共有 2 种 s 的循环移位，其 score 等于 k，因此答案为 2。

示例 2：

输入： s = "abca", k = 0

输出： 1

解释：

s 的所有循环移位为：

"abca"：不存在两个相邻且相同的字符，因此 score = 0。
"bcaa"：位置 2 和 3 处的字符相同，因此 score = 1。
"caab"：位置 1 和 2 处的字符相同，因此 score = 1。
"aabc"：位置 0 和 1 处的字符相同，因此 score = 1。

只有 1 种 s 的循环移位，其 score 等于 k，因此答案为 1。

提示：

2 <= n == s.length <= 100
s 仅由小写英文字母组成。
0 <= k <= n - 1

解法

方法一：模拟

记字符串长度为 \(n\)。我们先计算原串 \(s\) 的得分 \(\textit{score}\)，即满足 \(s[i] = s[i + 1]\)（\(0 \leq i < n - 1\)）的下标数量。若 \(\textit{score} = k\)，则将答案加 \(1\)。

接下来从原串出发，依次循环左移一位，共进行 \(n - 1\) 次。第 \(t\) 次左移（\(t = 0, 1, \ldots, n - 2\)）时，移到末尾的字符为 \(s[t]\)，得分仅有两处变化：

失去原先首部的相邻对，即 \(s[t]\) 与 \(s[t + 1]\)；
新增尾部的相邻对，即 \(s[t - 1]\) 与 \(s[t]\)。

其中下标对 \(n\) 取模。因此可以 \(O(1)\) 更新 \(\textit{score}\)，并统计得分等于 \(k\) 的循环移位数量。

时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。其中 \(n\) 是字符串 \(s\) 的长度。

Python3JavaC++GoTypeScript

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

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

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

4043. 恰好有 K 对相等相邻字符的循环移位数量

题目描述

解法

方法一：模拟

评论