小红切字符串

[题目链接](https://www.nowcoder.com/practice/f3ff2b43d0ee4c6ca7af9e93f81d382b)

思路

将字符串切成两个非空部分，要求两部分的"权值"相等。权值定义为辅音字母数和元音字母数之差的绝对值。

前缀和 + 数学推导

给每个字符赋值：辅音为 ，元音为 。设前缀和 为前 个字符的值之和，总和为 。

在位置 处切割（左边 个字符，右边 个字符），两部分的权值分别为：

$$

要求 ，即 等价于 或 ：

  • 情况一：，即 。
  • 情况二：，即 。

因此：

  • 若 ，则所有 个切割位置都合法（因为情况二恒成立）。
  • 若 且 为奇数，则 无整数解，答案为 。
  • 若 且 为偶数，统计满足 的切割位置数（）。

样例验证

字符串 arcaea，每个字符的值为 ，总和 。

前缀和：，需要 ，满足的位置为 和 ，答案为 。

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin >> s;
    int n = s.size();
    int total = 0;
    for(char c : s)
        total += (c=='a'||c=='e'||c=='i'||c=='o'||c=='u') ? -1 : 1;
    int ans = 0, pre = 0;
    for(int i = 0; i < n - 1; i++){
        pre += (s[i]=='a'||s[i]=='e'||s[i]=='i'||s[i]=='o'||s[i]=='u') ? -1 : 1;
        if(total == 0 || 2 * pre == total)
            ans++;
    }
    printf("%d\n", ans);
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int n = s.length();
        int total = 0;
        for (int i = 0; i < n; i++)
            total += isVowel(s.charAt(i)) ? -1 : 1;
        int ans = 0, pre = 0;
        for (int i = 0; i < n - 1; i++) {
            pre += isVowel(s.charAt(i)) ? -1 : 1;
            if (total == 0 || 2 * pre == total)
                ans++;
        }
        System.out.println(ans);
    }
    static boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}

复杂度分析

  • 时间复杂度：，一次遍历计算总和，一次遍历统计答案。
  • 空间复杂度：，只用了常数个变量（不计输入存储）。