题解 | #小红切字符串#

题目链接

小红切字符串

思路分析

1. 问题转换

题目要求我们将一个字符串 s 切割成两个非空部分 s_left 和 s_right，并计算有多少种切割点，使得 s_left 和 s_right 的“权值”相等。

一个字符串的权值定义为：|元音数量 - 辅音数量|。

为了方便计算，我们可以给每个字符赋予一个数值：

• 元音字母（a, e, i, o, u）记为 +1。
• 辅音字母记为 -1。

这样，一个字符串的“权值”就变成了 |其所有字符对应数值的总和|。

令 value(c) 为字符 c 对应的数值（+1 或 -1）。

• 对于左半部分 s_left，其数值总和为 。其权值为 。
• 对于右半部分 s_right，其数值总和为 。其权值为 。

我们要寻找的切割点，就是满足 的所有位置。

2. 核心关系与前缀和

令 total_value 为整个字符串 s 的所有字符的数值总和。 如果我们选择在索引 i 和 i+1 之间进行切割：

• 左半部分 s_left 是 s[0...i]。其数值和 可以通过前缀和快速计算。
• 右半部分 s_right 是 s[i+1...n-1]。其数值和 等于 total_value - V_{left}。

这样，条件 就变成了 。

3. 解方程

我们来解这个关于 的方程：。

这个方程有两种可能：

结论：

• 情况一：如果 total_value 不为 0，那么一个切割点是有效的，当且仅当它对应的左半部分的数值和 等于 total_value / 2。
• 情况二：如果 total_value 等于 0，那么一个切割点是有效的，当且仅当它对应的左半部分的数值和 满足 。这个等式对任意 都成立。因此，当 total_value 为 0 时，任何一个可能的切割点都是有效的。

4. 算法步骤

1. 预处理：

   a. 创建一个 is_vowel 的集合或布尔数组，用于快速判断一个字符是否是元音。

   b. 遍历整个字符串 s，计算出 total_value。

2. 情况判断：

   a. 如果 total_value 不为 0：

   i. 如果 total_value 是奇数，那么 total_value / 2 不是整数，不可能存在一个切割点满足条件。答案为 0。

   ii. 如果 total_value 是偶数，我们需要计算有多少个前缀 s[0...i] 的数值和等于 total_value / 2。

   iii. 我们可以再次遍历字符串，计算前缀和，统计满足条件的切割点数量。

   b. 如果 total_value 等于 0：

   i. 任何一个切割点都是有效的。

   ii. 字符串长度为 n，可以切割的位置有 n-1 个（在索引 0 和 1 之间，...，在索引 n-2 和 n-1 之间）。

   iii. 答案直接就是 n-1。

3. 最终实现：

   a. 计算 total_value。

   b. 如果 total_value == 0，输出 n-1。

   c. 如果 total_value % 2 != 0，输出 0。

   d. 否则，计算目标前缀和 target_prefix_value = total_value / 2。

   e. 初始化 count = 0, current_prefix_value = 0。

   f. 遍历字符串 s 从索引 i = 0 到 n-2（因为切割出的两个部分都不能为空）：

   • 更新 current_prefix_value。
   • 如果 current_prefix_value == target_prefix_value，则 count 加一。

   g. 输出 count。

代码

#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

bool is_vowel(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

void solve() {
    string s;
    cin >> s;
    int n = s.length();

    long long total_value = 0;
    for (char c : s) {
        if (is_vowel(c)) {
            total_value++;
        } else {
            total_value--;
        }
    }

    if (total_value == 0) {
        cout << n - 1 << endl;
        return;
    }

    if (total_value % 2 != 0) {
        cout << 0 << endl;
        return;
    }

    long long target_prefix_value = total_value / 2;
    long long count = 0;
    long long current_prefix_value = 0;

    // 遍历所有可能的切割点
    for (int i = 0; i < n - 1; ++i) {
        if (is_vowel(s[i])) {
            current_prefix_value++;
        } else {
            current_prefix_value--;
        }
        if (current_prefix_value == target_prefix_value) {
            count++;
        }
    }

    cout << count << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int n = s.length();

        Set<Character> vowels = new HashSet<>();
        vowels.add('a');
        vowels.add('e');
        vowels.add('i');
        vowels.add('o');
        vowels.add('u');

        long totalValue = 0;
        for (char c : s.toCharArray()) {
            if (vowels.contains(c)) {
                totalValue++;
            } else {
                totalValue--;
            }
        }

        if (totalValue == 0) {
            System.out.println(n - 1);
            return;
        }

        if (totalValue % 2 != 0) {
            System.out.println(0);
            return;
        }

        long targetPrefixValue = totalValue / 2;
        long count = 0;
        long currentPrefixValue = 0;

        for (int i = 0; i < n - 1; i++) {
            if (vowels.contains(s.charAt(i))) {
                currentPrefixValue++;
            } else {
                currentPrefixValue--;
            }
            if (currentPrefixValue == targetPrefixValue) {
                count++;
            }
        }

        System.out.println(count);
    }
}

import sys

def solve():
    try:
        s = sys.stdin.readline().strip()
    except (IOError, ValueError):
        return

    n = len(s)
    vowels = {'a', 'e', 'i', 'o', 'u'}
    
    total_value = 0
    for char in s:
        if char in vowels:
            total_value += 1
        else:
            total_value -= 1
            
    if total_value == 0:
        print(n - 1)
        return
        
    if total_value % 2 != 0:
        print(0)
        return
        
    target_prefix_value = total_value // 2
    count = 0
    current_prefix_value = 0
    
    for i in range(n - 1):
        if s[i] in vowels:
            current_prefix_value += 1
        else:
            current_prefix_value -= 1
        
        if current_prefix_value == target_prefix_value:
            count += 1
            
    print(count)

solve()

算法及复杂度

• 算法：前缀和
• 时间复杂度：，其中 是字符串的长度。我们只需要对字符串进行常数次遍历。
• 空间复杂度：，除了存储输入字符串外，我们只需要常数级别的额外空间。