#125

#GFG #POTD #geeksforgeeks #problemoftheday
In this video, I will be discussing Number of Distinct Subsequences.
👉🏻 Learn about Priority Queues - czcams.com/users/li...
👉🏻 Graphs Playlist - • Graphs
👉🏻 Tree/BST Playlist - • Binary Trees / BST
If you are new to the channel, please like this video, comment, and subscribe ❤️
Important Links -
▶️ Telegram - t.me/placement...
▶️ Instagram - / placementsready
▶️ Twitter - / placementsr
▶️ LinkedIn - / placementsready
▶️ Problem Link - practice.geeks...
▶️ Solution Link C++ - ideone.com/qYprZo
▶️ Solution Link JAVA - ideone.com/4mkSgw
▶️ Solution Link Python - ideone.com/Bb2SPS
🔥 Connect here for Mock Interviews, Resume Review, Interview Preparation etc. - topmate.io/avi...
number of distinct subsequences
number of distinct subsequences
number of distinct subsequences gfg
number of distinct subsequences easiest explanation
number of distinct subsequences c++
number of distinct subsequences java
number of distinct subsequences python
number of distinct subsequences explanation
code for number of distinct subsequences
number of distinct subsequences programming interview question
c program for number of distinct subsequences
program to find number of distinct subsequences
distinct subsequences
number of distinct subsequences leetcode
number of distinct subsequences interview bit solution c++
data structures and algorithms
number of distinct subsequences java
java number of distinct subsequences program
number of distinct subsequences program in java
number of distinct subsequences gfg
number of distinct subsequences gfg potd
number of distinct subsequences gfg solution
number of distinct subsequences explain
number of distinct subsequences solution c++
number of distinct subsequences solution java
number of distinct subsequences solution python
replace o with x
replace O with X
number of distinct subsequences solution java gfg solution
number of distinct subsequences solution c++ gfg problem solution
number of distinct subsequences c++ code
number of distinct subsequences java code
number of distinct subsequences python code
number of distinct subsequences c++ code
number of distinct subsequences java code
number of distinct subsequences python code
gfg number of distinct subsequences c++
gfg number of distinct subsequences java
gfg number of distinct subsequences python
gfg number of distinct subsequences problem
gfg potd number of distinct subsequences
today gfg potd number of distinct subsequences
potd gfg number of distinct subsequences
GFG POTD 02/10/23
Google Coding Interview Questions and Answer
distinct subsequences
distinct subsequence leetcode
distinct subsequence dynamic programming
distinct subsequences solution
distinct subsequence
distinct subsequence dp
dp distinct subsequence
count distinct subsequence
distinct subsequence solution
distinct subsequences ii
115 distinct subsequences
distinct subsequences leetcode
leetcode distinct subsequences
programming distinct subsequences
distinct palindromic subsequences
count distinct subsequence
count distinct palindromic subsequences
subsequence
distinct subsequence dynamic programming
distinct subsequences ii
115 distinct subsequences
distinct subsequence
distinct subsequence dp
dp distinct subsequence
leetcode distinct subsequences
distinct subsequences solution
distinct subsequence solution
distinct palindromic subsequences
how to solve gfg potd
how to solve today's gfg potd
solve gfg potd
gfg potd
gfg potd today solution
potd gfg
today gfg potd solution
problem of the day
gfg problem of the day
gfg potd today
gfg potd today solution
problem of the day gfg
problem of the day solution
geeksforgeeks practice
problem of the day gfg solution
geeksforgeeks potd
gfg practice problem
problem of the day
gfg problem of the day
leetcode problem of the day
daily problem
count the number of full binary trees
problem-solving classes
problem of the day gfg
gfg problem of days
practice coding problems
number of distinct balls in every bucket
leetcode September challenge
gfg problem
leetcode problem
leetcode problems
leetcode practice problem
how to solve the problem of the day geeks for geeks
geeksforgeeks
Problem Statement -
Given a string consisting of lower case 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.
Expected Time Complexity: O(|str|)
Expected Auxiliary Space: O(|str|)
Connect with me :
LinkedIn - / avinashkumarmallik

[@eklavya22k34]

Thanks for explaining , code is simple, only understanding is the main part.
It will be nice if u could explain 2 examples separately by making a full dig. from starting till all subsequences are covered. Once ex. is understood, code is doable if anyone has covered the basic.
Thanks again. Tc.

[@PlacementsReady]

Ok thanks for the suggestions

[@52nevil36]

thanks bro

[@abhishekkumar-gi5xm]

it is not necessary to make us understand in english ... hindi me smjhate to aacha rehta.. aur aache se smjh me aata

[@PlacementsReady]

Where u faced the issue ?

[@HarshGuptaNITP]

why you subtracted dp[index-1]? as the answer is stored in in dp[index]as dp[0]=1, dp[1]=2 so you are following one based indexing

[@PlacementsReady]

We need to ignore the subsequence that contains that character that is why index-1

[@sushantsuman4329]

why ggf output is 6 and gfg is 7? both are same

[@PlacementsReady]

Do a dry run according to algo u will understand

[@nithinn2632]

in string "gfg", why "ggf" and "fgg" is not a substring?

[@rainywinter459]

We are finding subsequences not substring

[@PlacementsReady]

Bro by mistake I told substring while explaining

[@PlacementsReady]

Order should be followed that's why ggf and fgg is not a subsequence

[@ScaraB01]

Can u tell in python

[@piyushverma1303]

def distinctSubsequences(self, s):
dp=[0]*(len(s)+1)
dp[0]=1
mp={}
for i in range(1,len(s)+1):
dp[i]=2*dp[i-1]
if s[i-1] in mp:
dp[i]=(dp[i]-dp[mp[s[i-1]]-1])%1000000007
mp[s[i-1]]=i
return dp[len(s)]

[@PlacementsReady]

For reference Java and python code is attached in description of video