Cknight and String

NC232327. Cknight and String

描述

Cknight gets a string $s$ of length $N$ $(1\leq N\leq 500000)$ . The string $s$ consists of only character "a" and character "b".

Cknight wants to make string $s$ chaotic. That is to say, string $s$ does not contain string "ab" as its substring.

Cknight can use several operations to achieve that.

In each operation, he can choose a position in $s$ and replace the corresponding letter with character "a" or character "b".

He wants to know the minimal number of operations required.

输入描述

One line containing string .

输出描述

Output the answer.

示例1

输入:

bbbaababa

输出:

说明:

In sample 1, modifying letters at position 6 and 8 is an optimal solution (suppose the string is 1-indexed).

示例2

输入:

aabbbbb

输出:

说明:

In sample 2, modifying letters at position 1 and 2 is an optimal solution.

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 16ms, 内存消耗: 1520K, 提交时间: 2022-01-06 14:44:47

#include <bits/stdc++.h>

using namespace std;
int ans, ans1;
int main() {
    string s;
    cin >> s;
    for (auto i: s) {
        if (i == 'a')  ans ++;
        if (ans && i == 'b') ans1 ++, ans --;
    }
    cout << ans1;
    return 0;
}

Python3 解法, 执行用时: 256ms, 内存消耗: 5696K, 提交时间: 2022-03-17 14:24:50

s = input()
b = 0
a = 0
len_s = len(s)
for i in range(len_s):
    if(s[i] == "a") :
        a += 1
    elif (s[i] == "b" and a):
        a -= 1
        b += 1
print(b)

上一题

下一题

详情