小红的元音距离

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

思路

题目定义字符串的"权值"为最远两个元音字母之间的距离。如果元音数量不超过 1，权值为 0。要求删除一些字母，使剩余字符串的权值尽可能大，问最多能删除多少个字母。

关键观察

在剩余字符串中，权值 = 最后一个元音的位置 - 第一个元音的位置（位置是在剩余字符串中的下标）。删除一个处于首尾元音之间的字符，会让剩余字符串变短，权值减少 1。因此，首尾元音之间的字符不能删。

而首个元音之前、末尾元音之后的字符，对权值没有正面贡献——删掉它们不会改变首尾元音之间的距离（反而删掉前面的会让首元音位置前移，但不影响两元音之间的字符数）。实际上删掉这些字符后，权值保持不变（首尾元音间的字符数不变），因此应该全部删掉。

分情况讨论

设原字符串长度为 ，第一个元音位置为 ，最后一个元音位置为 （0-indexed）。

• 元音数量 ：无论怎么保留，权值最大为 0。空串权值也是 0，直接删掉全部字符，答案为 。
• 元音数量 ：保留 区间内的所有字符，删掉区间外的。答案为 。

复杂度分析

• 时间复杂度：，遍历一次字符串找首尾元音。
• 空间复杂度：，存储输入字符串。

代码

[sol-C++]

#include <bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin >> s;
    int n = s.size();
    auto isVowel = [](char c){ return c=='a'||c=='e'||c=='i'||c=='o'||c=='u'; };
    int first = -1, last = -1;
    for(int i = 0; i < n; i++){
        if(isVowel(s[i])){
            if(first == -1) first = i;
            last = i;
        }
    }
    if(first == -1 || first == last){
        cout << n << endl;
    } else {
        cout << first + (n - 1 - last) << endl;
    }
    return 0;
}

[sol-Java]

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 first = -1, last = -1;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c=='a'||c=='e'||c=='i'||c=='o'||c=='u') {
                if (first == -1) first = i;
                last = i;
            }
        }
        if (first == -1 || first == last) {
            System.out.println(n);
        } else {
            System.out.println(first + (n - 1 - last));
        }
    }
}

[sol-Python3]

s = input()
n = len(s)
vowels = set('aeiou')
first = -1
last = -1
for i in range(n):
    if s[i] in vowels:
        if first == -1:
            first = i
        last = i
if first == -1 or first == last:
    print(n)
else:
    print(first + (n - 1 - last))

[sol-JavaScript]

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
rl.on('line', (line) => {
    const s = line.trim();
    const n = s.length;
    const vowels = new Set(['a','e','i','o','u']);
    let first = -1, last = -1;
    for (let i = 0; i < n; i++) {
        if (vowels.has(s[i])) {
            if (first === -1) first = i;
            last = i;
        }
    }
    if (first === -1 || first === last) {
        console.log(n);
    } else {
        console.log(first + (n - 1 - last));
    }
    rl.close();
});