题目描述

小O有一个长度为 $n$ 的数字字符串 $s$，他想知道 $s$ 中含有多少个 "1145" 子串序列。

"1145" 子串序列是指由两个连续的数字 "1"、一个数字 "4" 和一个数字 "5" 组成的字符串，在这里，我们依据数字在原字符串中的下标大小决定顺序。

解题思路

将连续的1数量做前缀和，5的数量做后缀和，遍历字符串，与到4的时候，将4前面的11和后面的5排列组合即为答案

代码

Python

def solution(n, s):
    MOD = 10**9 + 7
    prefix_11 = [0] * n