题解 | #字符串子串#

题目链接

字符串子串

题目描述

给定一个仅包含小写字母的字符串 $s$ 。请计算这个字符串的所有非空子串中，不包含字符 'd' 且同时包含字符 'r' 与 'e' 的子串数量。

【名词解释】子串：为从原字符串中，连续的选择一段字符（可以全选）得到的新字符串。

输入:

一个仅包含小写字母的字符串 $s$ 。

输出:

一个整数，表示满足条件的子串数量。

解题思路

这是一个子串计数问题。一个 $O(N^2)$ 的朴素解法是枚举所有子串，然后逐一检查是否满足条件，但这会超时。我们可以设计一个 $O(N)$ 的高效算法。

其核心思想是，当我们从左到右遍历字符串时，对于每个位置 $i$ ，我们计算有多少个以 $s[i]$ 结尾的子串满足条件。

一个以 $s[i]$ 结尾的子串 $s[j..i]$ （其中 $0 \le j \le i$ ）要满足条件，其起始位置 $j$ 必须遵循以下规则：

不包含 'd': 子串 $s[j..i]$ 中不能有 'd'。这意味着 $j$ 必须在最后一个 'd' 的后面。如果我们记录在位置 $i$ 之前（包括 $i$ ）遇到的最后一个 'd' 的位置为 $\text{last_d}$ ，那么必须满足 $j > \text{last_d}$ 。
包含 'r': 子串 $s[j..i]$ 中必须有 'r'。这意味着 $j$ 必须在最后一个 'r' 的前面或与之重合。如果我们记录在位置 $i$ 之前（包括 $i$ ）遇到的最后一个 'r' 的位置为 $\text{last_r}$ ，那么必须满足 $j \le \text{last_r}$ 。
包含 'e': 同理，如果我们记录在位置 $i$ 之前（包括 $i$ ）遇到的最后一个 'e' 的位置为 $\text{last_e}$ ，那么必须满足 $j \le \text{last_e}$ 。

综合这三个条件，对于结束位置 $i$ ，有效的起始位置 $j$ 必须满足： $\text{last_d} < j \le \min(\text{last_r}, \text{last_e})$

因此，在遍历到位置 $i$ 时，以 $s[i]$ 结尾的有效子串的数量就是 $\max(0, \min(\text{last_r}, \text{last_e}) - \text{last_d})$ 。我们将这个数量累加到总数中即可。

算法流程:

初始化总数 $\text{count} = 0$ ，以及三个位置指针 $\text{last_r} = -1, \text{last_e} = -1, \text{last_d} = -1$ 。
遍历字符串 $s$ 的每个字符 $s[i]$ （从 $i=0$ 到 $n-1$ ）： a. 更新指针：如果 $s[i]$ 是 'r', 'e', 或 'd'，则更新对应的 last 指针为当前位置 $i$ 。 b. 计算有效起点的上界，即 $\text{upper_bound} = \min(\text{last_r}, \text{last_e})$ 。 c. 有效起点的数量等于 $\max(0, \text{upper_bound} - \text{last_d})$ 。 d. 将此数量累加到总数 $\text{count}$ 中。
遍历结束后， $\text{count}$ 即为最终答案。

代码

cpp
java
python

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

using namespace std;

void solve() {
    string s;
    cin >> s;

    long long count = 0;
    int last_r = -1;
    int last_e = -1;
    int last_d = -1;

    for (int i = 0; i < s.length(); ++i) {
        // 更新最近一次出现的位置
        if (s[i] == 'r') {
            last_r = i;
        } else if (s[i] == 'e') {
            last_e = i;
        } else if (s[i] == 'd') {
            last_d = i;
        }

        // 计算有效起点的上界
        int upper_bound = min(last_r, last_e);
        // 有效起点的下界是 last_d
        
        // 如果存在有效范围 [last_d + 1, upper_bound]，则累加其长度
        if (upper_bound > last_d) {
            count += (long long)(upper_bound - last_d);
        }
    }

    cout << count << endl;
}

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

import java.util.Scanner;
import java.lang.Math;

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

        long count = 0;
        int lastR = -1;
        int lastE = -1;
        int lastD = -1;

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            // 更新最近一次出现的位置
            if (ch == 'r') {
                lastR = i;
            } else if (ch == 'e') {
                lastE = i;
            } else if (ch == 'd') {
                lastD = i;
            }

            // 计算有效起点的上界
            int upperBound = Math.min(lastR, lastE);
            // 有效起点的下界是 lastD
            
            // 如果存在有效范围 [lastD + 1, upperBound]，则累加其长度
            if (upperBound > lastD) {
                count += (long)(upperBound - lastD);
            }
        }

        System.out.println(count);
    }
}

def solve():
    s = input()
    
    count = 0
    last_r = -1
    last_e = -1
    last_d = -1
    
    for i, char in enumerate(s):
        # 更新最近一次出现的位置
        if char == 'r':
            last_r = i
        elif char == 'e':
            last_e = i
        elif char == 'd':
            last_d = i
        
        # 计算有效起点的上界
        upper_bound = min(last_r, last_e)
        # 有效起点的下界是 last_d
        
        # 如果存在有效范围 [last_d + 1, upper_bound]，则累加其长度
        if upper_bound > last_d:
            count += (upper_bound - last_d)
            
    print(count)

solve()

算法及复杂度

算法：单指针扫描 (One-pass)
时间复杂度: $O(N)$ ，其中 $N$ 是字符串的长度，因为我们只对字符串进行了一次遍历。
空间复杂度: $O(N)$ ，用于存储输入的字符串。如果输入是流式处理的，则空间复杂度为 $O(1)$ 。