You are provided an input string S and the string “GEEKS” . Find the number of ways in which the subsequence “GEEKS” can be formed from the string S.
 
Example 1:
Input : S = "GEEKS"
Output: 1
Explanation: 
"GEEKS" occurs in S only once.
Example 2:
Input: S = "AGEEKKSB"
Output: 2
Explanation: Subsequenece "GEEKS" occurs in 
S two times. First one is taking the first 
'K' into consideration and second one is 
taking second 'K'.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function TotalWays() which takes string S as input paramater and returns total ways modulo 10^{9} + 7.
 
Expected Time Complexity : O(N * K) where N is length of string and K is constant.
Expected Space Complexity: O(N * K)
 
Constraints: 
1 <= Length od string <= 10000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

	def TotalWays(self, str):

		# Code here

Solutions:
class Solution:

	def TotalWays(self, s1):
		mod = int(1000000000.0 + 7)
		s2 = 'GEEKS'
		dp = [[0 for i in range(len(s2) + 1)] for j in range(len(s1) + 1)]
		dp[0][0] = 1
		for i in range(1, len(s1) + 1):
			dp[i][0] = 1
		for i in range(1, len(s1) + 1):
			for j in range(1, len(s2) + 1):
				if s1[i - 1] == s2[j - 1]:
					dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % mod
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[len(s1)][len(s2)]


class Solution:

	def TotalWays(self, str):
		mod = 10 ** 9 + 7
		s1 = 'GEEKS'
		s2 = str
		n = len(s1)
		m = len(s2)
		dp = [[-1 for x in range(m + 1)] for y in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = 0
		for j in range(m + 1):
			dp[0][j] = 1
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if s1[i - 1] == s2[j - 1]:
					dp[i][j] = (dp[i - 1][j - 1] + dp[i][j - 1]) % mod
				else:
					dp[i][j] = dp[i][j - 1] % mod
		return dp[n][m]


class Solution:

	def TotalWays(self, str):
		dp = []
		s = 'GEEKS'
		for i in range(len(str) + 1):
			x = []
			for j in range(len(s) + 1):
				if j == 0:
					x.append(1)
				else:
					x.append(0)
			dp.append(x)
		for i in range(1, len(str) + 1):
			for j in range(1, len(s) + 1):
				if str[i - 1] == s[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[len(str)][len(s)] % 1000000007


class Solution:

	def TotalWays(self, str):
		n = len(str)
		temp = 'GEEKS'
		m = 5
		mod = 10 ** 9 + 7
		dp = [[0 for j in range(m + 1)] for i in range(n + 1)]
		for i in range(n + 1):
			for j in range(m + 1):
				if j == 0:
					dp[i][j] = 1
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if str[i - 1] == temp[j - 1]:
					dp[i][j] = (dp[i - 1][j - 1] % mod + dp[i - 1][j] % mod) % mod
				else:
					dp[i][j] = dp[i - 1][j] % mod
		return dp[n][m] % mod


def solve(s1, s2='GEEKS', i=0, j=0):
	global mod
	global dp
	try:
		return dp[i, j]
	except:
		pass
	if j >= len(s2):
		return 1
	if i >= len(s1):
		return 0
	if s1[i] != s2[j]:
		dp[i, j] = solve(s1, s2, i + 1, j) % mod
		return dp[i, j]
	dp[i, j] = (solve(s1, s2, i + 1, j + 1) % mod + solve(s1, s2, i + 1, j) % mod) % mod
	return dp[i, j]

class Solution:

	def TotalWays(self, str):
		s1 = 'GEEKS'
		s2 = str
		dp = [[0 for i in range(len(s2) + 1)] for j in range(6)]
		mod = 1000000007
		for i in range(len(s2)):
			dp[0][i] = 1
		for i in range(1, 6):
			for j in range(1, len(s2) + 1):
				if s1[i - 1] != s2[j - 1]:
					dp[i][j] = dp[i][j - 1] % mod
				else:
					dp[i][j] = (dp[i - 1][j - 1] % mod + dp[i][j - 1] % mod) % mod
		return dp[-1][-1]


class Solution:

	def TotalWays(self, str):
		s1 = str
		s2 = 'GEEKS'
		n = len(str)
		m = 10 ** 9 + 7
		dp = [[0] * 6 for ele in range(n + 1)]
		dp[0][0] = 1
		for i in range(n + 1):
			dp[i][0] = 1
		for i in range(1, n + 1):
			for j in range(1, 6):
				dp[i][j] = dp[i - 1][j]
				if s1[i - 1] == s2[j - 1]:
					dp[i][j] += dp[i - 1][j - 1] % m
		return dp[n][5] % m