T1

题目描述

给定一个字符串序列，包含字母、数字以及空格，请问该字符串最多能组成多少个“Good”。字符串区分大小写，每个字符只能使用一次，且不能调换字符顺序。

输入描述

每行输入一个字符串，字符串长度小于100000。

输出描述

输出该字符串能组成的最大“Good”个数

示例1

样例输入

ggoodood

样例输出

0

示例2

样例输入

Goo23good Gooddd

样例输出

2

示例3

样例输入

123 GoodoodGGoooddjfhjdGGooo3dkdggggGoood0123\n

样例输出

5

算法

(枚举) $O(n)$

1. bool数组保存每个字符是否被使用过
2. 每遇到一个G，向后寻找最近的2个o和1个d，找到了就更新答案，没找到就结束查找

时间复杂度

字符串会被枚举一遍，时间复杂度为$O(n)$；额外使用$O(n)$的空间存放每个字符是否使用

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

int ret;
string s;
vector<bool> st;

int main() {
    getline(cin, s);

    st = vector<bool>(s.size(), false);

    for (int i = 0; i < s.size(); i ++ )
        if (s[i] == 'G') {
            st[i] = true;
            int j = i, cnt_o = 0, cnt_d = 0;
            while (j < s.size() && cnt_o < 2) {
                if (s[j] == 'o' && !st[j]) cnt_o ++ , st[j] = true;
                j ++ ;
            }

            if (cnt_o == 2) {
                while (j < s.size() && cnt_d < 1) {
                    if (s[j] == 'd' && !st[j]) cnt_d ++ , st[j] = true;
                    j ++ ;
                }
                if (cnt_d == 1) ret ++ ;
                else break;
            } else break;
        }

    cout << ret;

    return 0;
}

T2

T3