超市里正在举行打折活动，每隔 n 个顾客会得到 discount 的折扣。超市里有一些商品，第 i 种商品为 products[i] 且每件商品的价格为 prices[i]。
结账系统会统计顾客的数目，每隔 n 个顾客结账时，该顾客的账单都会打折，折扣为 discount，然后系统会重新开始计数。
顾客会购买一些商品，product[i] 是顾客购买的第 i 种商品，amount[i] 是对应的购买该种商品的数目。
这道题目给的条件相对比较多，需要仔细阅读条件，
注意
几个变量之间的下标关系
，具体实现代码如下：
![]()
给你一个字符串 S ，它只包含三种字符 a，b，c 。请返回 a，b 和 c 都至少出现过一次的子字符串的数目。
通过暴力枚举，可以在 O(n^2) 的时间复杂度内统计合法的子串。
对于字符串 [0, i]，如果 [0, j] 为合法字串，那么 [0, j+1] 必然也为合法字串。
利用上述特性，可以减少内循环的次数，具体实现代码如下：
![]()
但是，本道题 O(n^2) 的时间复杂度是没法 AC 的。
从上述暴力枚举的过程中，可以发现只要找到
最小的合法字串
，其他包含该字串的数目很容易计算。
而对于任意一个子串，无非就是开始下标和结束下标，那么就可以采用双指针技巧，将时间复杂度降低为 O(n)
。
![]()
再利用哈希表记录当前子串中字符的状态，从而减少子串验证合法性的时间复杂度。
![]()
给你 n 笔订单，每笔订单都需要快递服务。请你统计所有有效的收件/配送 序列的数目，请确保第 i 个物品的配送服务 delivery(i) 总是在其收件服务 pickup(i) 之后。
由于答案可能很大，请返回答案对 10^9 + 7 取余的结果。
这是一道
动态规划
的题目，可以定义
dp[i] 表示 i 笔订单有效序列的个数
。
由上述题目中给出的信息，可以很容易知道：
那么当 i = 2 时，可以基于 i = 1 进行如下操作得到所有有效序列。
第一种情况：
将 P2D2 合并在一起插入到前一个状态中
。
![]()
第二种情况：将 P2D2 分开插入，保证 P2 在 D2 之前。
![]()
根据上述推导过程，可以得到如下状态转移方程：
![]()
由推导公式，可以发现下一个状态只与前一个状态有关系，那么就没必要利用数组记录无关的状态，时间复杂度可以降低为 O(1)。
最后千万不要忘记对结果取余哦。
![]()
![]()
