这是一个经典的单遍扫描动态规划(计数)问题。我们希望在原字符串 s 中找出所有不同的子序列恰好等于 "abc" 的种数。由于 d 字符不参与目标子序列,可以直接忽略。
算法维护三个计数器:
count_a:记录从开始到当前位置,已经出现的字符 'a' 的个数;count_ab:记录从开始到当前位置,可以构成子序列 "ab" 的种数;count_abc:记录从开始到当前位置,可以构成子序列 "abc" 的种数。小蓝正在分析一条自动化流水线的操作日志。日志由若干条记录顺序组成,每条记录用一个字符表示,可能是 a、b、c 或 d,分别对应四种不同类型的动作。
在分析过程中,小蓝发现一个完整的标准作业流程恰好需要依次执行动作 a、动作 b 和动作 c。换句话说,如果从整个日志序列中可以抽取出一个子序列恰好等于 abc,就代表完成了一次标准作业。子序列是指从原序列中删除任意个(可以为 0 个,也可以为全部)字符,保持剩余字符的相对顺序得到的新序列。
现在给定一个操作日志字符串,请你计算出在该日志中,一共存在多少种不同的方式可以抽出子序列 abc。
字符串仅由字符 a、b、c、d 组成,长度 n 满足 1 ≤ n ≤ 10^5。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册