Subsequence Count

Problem Preview

"Given two strings, find out how many times the first string appears as a subsequence within the second string. A subsequence is formed by removing any number of characters (including zero) from a string without altering the order of the remaining characters. ### Problem Given two strings, find out how many times the first string appears as a subsequence within the second string. ### Example 1: s1 = "ABC" s2 = "ABCBA" The string s1 appears 5 times as a subsequence in s2 at 1-indexed positions of {1, 2, 3}, {1, 2, 7}, {1, 4, 7}, {1, 5, 6, 7}, and {5, 6, 7}. The answer is 5. ### Example 2: s1 = "HRW" s2 = "HERHRWS" The string s1 appears 3 times as a subsequence in s2. ### Example 3: s1 = "ELO" s2 = "HELLO WORLD" The string s1 appears 4 times as a subsequence in s2. ### Input Two strings s1 and s2. ### Output The number of times s1 appears as a subsequence in s2. ### Constraints - length of s1 = 3 - 1 ≤ length of s2 ≤ 5*10^5 - s1 and s2 consist of uppercase English letters, A-Z."