偏爱字母 #

发布于2021-04-16

上次编辑2021-04-16

问题描述#

小美喜欢字母 E ，讨厌字母 F 。在小美生日时，小团送了小美一个仅包含字母 E 和 F 的字符串，小美想从中选出一个包含字母 E 数量与字母 F 数量之差最大的子串。
*子串：从字符串前面连续删去若干个字符，从后面连续删去若干个字符剩下的字符串（也可以一个都不删），例如 abcab 是 fabcab 的子串，而不是 abcad 的子串。我们将空串看作所有字符串的子串。

格式：
输入：
- 第一行一个正整数 n 表示字符串的长度。  
- 第二行长度为 n ，且仅包含大写字母 'E', 'F' 的字符串（不含引号）
输出：
- 输出一个整数，表示最大的差值。
示例：
输入：
     5
     EFEEF
输出：2
解释：
选择子串 EE ，此时有 2 个 E ，0 个 F ，有最大差值 2-0=2
另外，选择子串 EFEE 也可以达到最大差值。
提示：

对于 30% 的数据，n <= 300

对于 60% 的数据，n <= 3000

对于 100% 的数据，n <= 300000

解题思路#

滑动窗口。

Python

import sys
from typing import List

readline = sys.stdin.readline


def readint() -> int:
    return int(readline().strip())


def readstr() -> str:
    return readline().strip()


def readints() -> List[int]:
    return list(map(int, readline().strip().split()))


n = readint()
s = readstr()
ans = t = 0
for c in s:
    if c == 'E':
        t += 1
    else:
        t -= 1
    t = max(0, t)
    ans = max(ans, t)
print(ans)

C++

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    string s;
    cin >> n >> s;
    int ans = 0, t = 0;
    for (char c : s) {
        if (c == 'E') {
            t += 1;
        } else {
            t -= 1;
        }
        t = max(0, t);
        ans = max(ans, t);
    }
    cout << ans << '\n';
    return 0;
}

偏爱字母# 发布于2021-04-16 上次编辑2021-04-16

问题描述#

解题思路#

偏爱字母 #

发布于2021-04-16

上次编辑2021-04-16