美团2024秋招编程题：小美的red子序列数量之和

本文主要是介绍美团2024秋招编程题：小美的red子序列数量之和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目为：

小美有一个字符串，小美想知道这个字符串的所有连续子串中，red 子序列的数量之和。
子串是指从原字符串中，连续的选择一段字符组成的新字符串。
定义 red 子序列为从原字符串中从左到右依次取出r、e和d组成的新字符串。

输入描述

第一行输入一个长度不超过10^5、且仅由小写字母构成的字符串s，代表小美的字符串。

输出描述

在一行上输出一个整数，代表所有子串中 red 子序列的数量之和。由于答案可能很大，请将答案对(10^9十7)取模后输出。

示例 1
输入

redd

输出

3

说明

在 red 子串中，有1个red 子序列;
在 redd 子串中，有 2个red 子序列:

接替代码：

def count_red_subsequences(s):MOD = 10**9 + 7n = len(s)red_count = 0for j in range(n-2):dp = [[0] * 3 for _ in range(n)]for i in range(j, n):if s[i] == 'r':dp[i][0] = 1 + (dp[i-1][0] if i > 0 else 0)if s[i] == 'e':if i > 0:dp[i][1] = dp[i-1][1] + dp[i-1][0]if s[i] == 'd':if i > 0:dp[i][2] = dp[i-1][2] + dp[i-1][1]if i > 0:# dp[i][0] = (dp[i][0] + dp[i-1][0]) % MODdp[i][2] = (dp[i][2] + dp[i-1][2]) % MODif s[i] == 'd':red_count = (red_count + dp[i][2]) % MODreturn red_count

题解

dp[i][0]表示以第i个字符结尾的子串钟r的数量
dp[i][1]表示以第i个字符结尾的子串钟re的数量
dp[i][2]表示以第i个字符结尾的子串钟red的数量

两层for循环遍历，计算第j个字符开始第i个字符结尾的子串钟，red子序列的全部数量。
dp[i][2] = (dp[i][2] + dp[i-1][2]) % MOD重点是这句计算了s[j:i]中，s[j:i-1]中red子序列加上s[j:i]中red子序列之和。这样就成功计算了所有连续子串中的red子序列之和。