Problem statement

https://binarysearch.com/problems/ABC-Subsequences/

Solution

Equal to Leetcode 1955. Count Number of Special Subsequences.

Complexity

It is O(n) for time and O(1) for space.

Code

class Solution:
    def solve(self, s):
        s = [ord(x) - 97 for x in s]
        dp = [1, 0, 0, 0]
        for i in s:
            dp[i+1] = (2*dp[i+1] + dp[i])
        return dp[-1]