Day 65 of 100 days dsa coding challenge

Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀

100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney

Problem:

https://www.geeksforgeeks.org/problems/number-of-distinct-subsequences0909/1

Number of distinct subsequences

Difficulty: Hard Accuracy: 30.43%

Given a string str consisting of lowercase english alphabets, the task is to find the number of distinct subsequences of the string
Note: Answer can be very large, so, ouput will be answer modulo 109+7.
Examples:
Input: str = "gfg"
Output: 7
Explanation:
The seven distinct subsequences are "", "g", "f", "gf", "fg", "gg" and "gfg" .
Input: str = "ggg"
Output: 4
Explanation:
The four distinct subsequences are "", "g", "gg", "ggg".
Constraints:
1 ≤ |str| ≤ 105
str contains lower case English alphabets

Solution:
class Solution:
def distinctSubseq(self, s):
mod = 10**9 + 7
dp = 1
last = [0] * 26
for c in s:
x = dp
dp = (dp * 2 - last[ord(c) - 97]) % mod
last[ord(c) - 97] = x
return dp % mod