题目链接

小红的元音距离

题目描述

小红定义一个字符串的权值是：最远的两个元音的距离（即它们在字符串中的下标差）。

  • 例如，"xiaohongshu" 中，第一个元音 'i' 在下标 1，最后一个元音 'u' 在下标 10，则权值为 。
  • 特殊地，如果一个字符串的元音数量不超过 1 个，则认为权值是 0。

现在给定一个字符串，小红需要删除一部分字母（可以不删，也可以全删），使得剩余字符串的权值尽可能大。在满足权值最大的前提下，小红想知道，最多可以删除多少个字母？

注：元音字母仅包含 "a", "e", "i", "o", "u"。

思路分析

这是一个逆向思维的优化问题。题目要求“最多可以删除多少个字母”，这等价于求解“最少需要保留多少个字母”，同时要满足“使剩余字符串的权值最大化”的条件。

1. 如何最大化权值？

字符串的权值（元音距离）取决于其第一个元音和最后一个元音的位置。设一个字符串为 ，其长度为 ，第一个元音在下标 ，最后一个元音在下标 ，则权值为 。这个权值的最大值是 ，仅当第一个字符和最后一个字符都是元音时取到。

要使我们构造的子序列的权值最大，我们应该选择原字符串 中物理位置最靠前的元音作为子序列的第一个元音，并选择 中物理位置最靠后的元音作为子序列的最后一个元音。

设 中第一个元音的下标为 ，最后一个元音的下标为 。我们保留 中从 到 的所有字符，形成子串 。这个子串是一个合法的子序列，它的第一个元音在下标 （在新串中是下标 0），最后一个元音在下标 （在新串中是下标 ）。这个新串的权值为 。

可以证明，这是能得到的最大权值。任何其他的保留方案（例如，删除 之间的某个字符）都会使最终的字符串变短，从而导致权值减小。

2. 如何最少化保留？

在确定了最大权值为 后，我们需要找到实现这个权值的最短子序列。根据上面的分析，最短的、能实现这个权值的子序列就是子串 本身。其长度为 。

因此，最少需要保留的字符数为 。

3. 特殊情况

当原字符串 中元音的数量为 0 或 1 时，我们无论如何操作，得到的子序列的元音数量都不会超过 1，其权值最大只能为 0。 在这种情况下，为了最大化删除数量（即最小化保留数量），我们应该删除所有字符，得到一个空字符串。空串的权值为 0，满足条件。此时，删除的字母数为字符串的原始长度 。

4. 算法流程

  1. 遍历字符串，找到第一个元音的下标 和最后一个元音的下标 。同时，统计元音的总数。
  2. 如果元音总数小于等于 1，则答案为字符串的原始长度 。
  3. 如果元音总数大于 1，则最少需要保留的字符数为 。最多可以删除的字符数为 。

代码

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

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

int main() {
    string s;
    cin >> s;

    int first_vowel_idx = -1;
    int last_vowel_idx = -1;
    int vowel_count = 0;
    
    for (int i = 0; i < s.length(); ++i) {
        if (is_vowel(s[i])) {
            if (first_vowel_idx == -1) {
                first_vowel_idx = i;
            }
            last_vowel_idx = i;
            vowel_count++;
        }
    }

    if (vowel_count <= 1) {
        cout << s.length() << endl;
    } else {
        int kept_len = last_vowel_idx - first_vowel_idx + 1;
        cout << s.length() - kept_len << endl;
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    private static boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }

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

        int firstVowelIdx = -1;
        int lastVowelIdx = -1;
        int vowelCount = 0;

        for (int i = 0; i < s.length(); i++) {
            if (isVowel(s.charAt(i))) {
                if (firstVowelIdx == -1) {
                    firstVowelIdx = i;
                }
                lastVowelIdx = i;
                vowelCount++;
            }
        }

        if (vowelCount <= 1) {
            System.out.println(s.length());
        } else {
            int keptLen = lastVowelIdx - firstVowelIdx + 1;
            System.out.println(s.length() - keptLen);
        }
    }
}

def is_vowel(c):
    return c in "aeiou"

s = input()
n = len(s)

first_vowel_idx = -1
last_vowel_idx = -1
vowel_count = 0

for i, char in enumerate(s):
    if is_vowel(char):
        if first_vowel_idx == -1:
            first_vowel_idx = i
        last_vowel_idx = i
        vowel_count += 1

if vowel_count <= 1:
    print(n)
else:
    kept_len = last_vowel_idx - first_vowel_idx + 1
    print(n - kept_len)

算法及复杂度

  • 算法：单次遍历

  • 时间复杂度：。

    • 我们只需要对输入的字符串进行一次完整的遍历，以找到第一个和最后一个元音的位置。

  • 空间复杂度：。

    • 我们只需要几个额外的变量来存储下标和计数，空间开销是常数级别的。