Given two strings S and W. Find the number of times W appears as a subsequence of string S where every character of string S can be included in forming at most one subsequence.
 
Example 1:  
Input: 
 S = "abcdrtbwerrcokokokd" 
 W = "bcd" 
Output: 
 2
Explanation: 
The two subsequences of string W are
{ S_{1} , S_{2} , S_{3} } and { S_{6}_{ }, S_{11} , S_{18} }
(Assuming 0- based indexing).
 
Example 2: 
Input: 
S = "ascfret" 
W = "qwer" 
Output: 
0
Explanation:
No valid subsequences are possible.
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function numberOfSubsequences() which takes the string S and string W as input parameters and returns the number of subsequences of string W in string S.
 
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N)
 
Constraints:
1<=|S|<=1000
1<=|W|<=|S|

Difficulty: MEDIUM
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3

class Solution:

    def numberOfSubsequences (self,S,W):

        # code here 

Solutions:
class Solution:

	def numberOfSubsequences(self, S, W):
		ans = 0
		vis = [False] * len(S)
		for i in range(len(S)):
			if S[i] == W[0] and (not vis[i]):
				vis[i] = True
				j = i + 1
				k = 1
				while j < len(S) and k < len(W):
					if S[j] == W[k] and (not vis[j]):
						vis[j] = True
						k += 1
					j += 1
				if k == len(W):
					ans += 1
				else:
					break
		return ans


import itertools

class Solution:

	def numberOfSubsequences(self, S, W):
		S = list(S)
		(n1, n2, Spos, Wpos, count) = (len(S), len(W), 0, 0, 0)
		while Spos < n1:
			if S[Spos] == W[Wpos]:
				(S[Spos], Wpos) = ('#', Wpos + 1)
			Spos += 1
			if Wpos == n2:
				(Spos, Wpos, count) = (0, 0, count + 1)
		return count


class Solution:

	def numberOfSubsequences(self, s, w):
		s = list(s)
		c = 0
		for i in range(len(s)):
			k = 0
			j = i
			while j < len(s):
				if s[j] == w[k]:
					k += 1
					s[j] = 0
					if k == len(w):
						c += 1
						j = i - 1
						k = 0
				j += 1
		return c


class Solution:

	def numberOfSubsequences(self, S, pat):
		arr = []
		for elm in S:
			if elm in pat:
				arr.append(elm)
		if len(arr) < len(pat):
			return 0
		ans = 0
		for i in range(len(arr)):
			k = 0
			j = i
			while j < len(arr):
				if arr[j] == pat[k]:
					k += 1
					arr[j] = '0'
				if k == len(pat):
					ans += 1
					j = i - 1
					k = 0
				j += 1
		return ans


class Solution:

	def numberOfSubsequences(self, s, w):
		stk = []
		ans = 0
		x = w[-1]
		d = {}
		for i in w:
			if i not in d.keys():
				d[i] = 1
			else:
				d[i] += 1
		i = 0
		while i < len(s):
			if s[i] in d.keys():
				stk.append(s[i])
				if s[i] == x:
					p = len(stk)
					j = 0
					k = 0
					dup = []
					while j < p:
						if stk[0] == w[k]:
							dup.append(stk.pop(0))
							k += 1
						else:
							dup.append(stk[0])
							stk.append(stk.pop(0))
						if k == len(w):
							ans += 1
							break
						j += 1
					if k != len(w):
						stk = dup
			i += 1
		return ans


class Solution:

	def numberOfSubsequences(self, S, W):
		ans = 0
		p = [0] * len(S)
		(i, j, k) = (0, 0, 0)
		a = len(S)
		b = len(W)
		while i < a:
			if S[i] == W[0] and p[i] == 0:
				p[i] = 1
				j = 1
				k = i + 1
				while j < b and k < a:
					if S[k] == W[j] and p[k] == 0:
						p[k] = 1
						k += 1
						j += 1
					else:
						k += 1
				if j == b:
					ans += 1
			i += 1
		return ans


class Solution:

	def numberOfSubsequences(self, S, W):
		l1 = len(S)
		l2 = len(W)
		c = 0
		new = '1'
		if l1 == l2:
			j = 0
			for i in range(0, l1):
				if S[i] == W[j]:
					j = j + 1
			if j == l2:
				return 1
		for i in range(0, l1):
			j = 0
			if S[i] == W[j]:
				k = i + 1
				j = j + 1
				if k == l1:
					break
				while j < l2:
					if S[k] == W[j]:
						j = j + 1
						temp = list(S)
						temp[k] = new
						S = ''.join(temp)
					k = k + 1
					if k == l1:
						break
			if j == l2:
				c = c + 1
			else:
				continue
		return c


class Solution:

	def numberOfSubsequences(self, S, W):
		S = list(S)
		counter = 0
		for i in range(len(S)):
			k = 0
			for j in range(i, len(S)):
				if S[j] == W[k]:
					k += 1
					S[j] = '*'
				if k == len(W):
					counter += 1
					break
		return counter


class Solution:

	def numberOfSubsequences(self, S, W):
		ans = int()
		s = [char for char in S]
		w = [char for char in W]
		(i, j) = [0] * 2
		while i < len(s) and j < len(w):
			if s[i] == w[j]:
				s[i] = 'dinesh'
				i += 1
				j += 1
			else:
				i += 1
			if len(w) == j:
				ans += 1
				(i, j) = [0] * 2
		return ans


class Solution:

	def numberOfSubsequences(self, S, W):
		S = list(S)
		W = list(W)
		ans = 0
		while True:
			i = 0
			j = 0
			flag = 0
			while i < len(S):
				if S[i] == W[j]:
					j += 1
					S[i] = '*'
					if j == len(W):
						ans += 1
						flag = 1
						break
				i += 1
			if flag == 0:
				break
		return ans


class Solution:

	def numberOfSubsequences(self, s, w):
		s = list(s)
		(n, m) = (len(s), len(w))
		(i, j) = (0, 0)
		count = 0
		while i < n:
			if s[i] == w[j]:
				s[i] = '+'
				j += 1
			i += 1
			if j == m:
				i = 0
				j = 0
				count += 1
		return count


class Solution:

	def numberOfSubsequences(self, S, W):
		S = list(S)
		c = 0
		for i in range(len(S)):
			a = 0
			for j in range(i, len(S)):
				if S[j] == W[a]:
					a += 1
					S[j] = '*'
				if a == len(W):
					c += 1
					break
		return c


class Solution:

	def numberOfSubsequences(self, S, W):
		S = list(S)
		(a1, a2, Sp, Wp, count) = (len(S), len(W), 0, 0, 0)
		while Sp < a1:
			if S[Sp] == W[Wp]:
				(S[Sp], Wp) = ('#', Wp + 1)
			Sp += 1
			if Wp == a2:
				(Sp, Wp, count) = (0, 0, count + 1)
		return count


class Solution:

	def numberOfSubsequences(self, s, w):
		m = len(w)
		removed = set()
		ans = 0
		while True:
			j = 0
			for i in range(len(s)):
				if s[i] == w[j] and i not in removed:
					j += 1
					removed.add(i)
					if j == m:
						ans += 1
						break
			else:
				return ans


class Solution:

	def numberOfSubsequences(self, S, W):
		ans = 0
		dp = [0] * len(S)
		i = 0
		j = 0
		k = 0
		while i < len(S):
			if S[i] == W[0] and dp[i] == 0:
				dp[i] = 1
				j = 1
				k = i + 1
				while j < len(W) and k < len(S):
					if S[k] == W[j] and dp[k] == 0:
						dp[k] = 1
						k += 1
						j += 1
					else:
						k += 1
				if j == len(W):
					ans += 1
			i += 1
		return ans


class Solution:

	def numberOfSubsequences(self, S, W):
		s = list(S)
		ls = len(S)
		lw = len(W)
		(sp, wp, count) = (0, 0, 0)
		while sp < ls:
			if s[sp] == W[wp]:
				(s[sp], wp) = ('$', wp + 1)
			sp += 1
			if wp == lw:
				(sp, wp, count) = (0, 0, count + 1)
		return count


class Solution:

	def numberOfSubsequences(self, S, W):
		S = list(S)
		c = 0
		(n1, n2, sp, wp) = (len(S), len(W), 0, 0)
		while sp < n1:
			if S[sp] == W[wp]:
				(S[sp], wp) = ('*', wp + 1)
			sp += 1
			if wp == n2:
				(wp, sp, c) = (0, 0, c + 1)
		return c


class Solution:

	def numberOfSubsequences(self, S, W):
		S = list(S)
		ans = i = j = 0
		while i < len(S):
			if S[i] == W[j]:
				S[i] = '$'
				j += 1
			if j == len(W):
				ans += 1
				j = i = 0
			else:
				i += 1
		return ans


from collections import deque

class Solution:

	def numberOfSubsequences(self, s, w):
		ans = 0
		visited = [0 for _ in range(len(s))]
		i = 0
		j = 0
		while i < len(s):
			if s[i] == w[j] and visited[i] == 0:
				visited[i] == 1
				j = j + 1
				k = i + 1
				while k < len(s) and j < len(w):
					if s[k] == w[j] and visited[k] == 0:
						visited[k] = 1
						j = j + 1
					k = k + 1
				if j == len(w):
					ans += 1
					j = 0
				else:
					return ans
			i = i + 1
		return ans


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def numberOfSubsequences(self, S, W):
		visit = set()

		def dfs(i, j):
			nonlocal visit
			if i == len(S) or j == len(W):
				if j == len(W):
					visit = visit.union(curr)
					return 1
				else:
					return 0
			if i in visit:
				return dfs(i + 1, j)
			elif S[i] == W[j]:
				curr.add(i)
				return dfs(i + 1, j + 1)
			else:
				return dfs(i + 1, j)
		res = 0
		for i in range(len(S)):
			if i not in visit and S[i] == W[0]:
				curr = set()
				res += dfs(i, 0)
		return res


class Solution:

	def numberOfSubsequences(self, S, W):
		S = list(S)
		count = 0
		for i in range(len(S)):
			if S[i] == W[0]:
				current_x = 0
				for j in range(i, len(S)):
					if S[j] == W[current_x]:
						current_x += 1
						S[j] = '#'
						if current_x == len(W):
							count += 1
							break
		return count


class Solution:

	def numberOfSubsequences(self, S, W):
		res = 0
		v = [False] * len(S)
		for i in range(len(S)):
			if S[i] == W[0]:
				(a, b) = (i, 0)
				while a < len(S) and b < len(W):
					if S[a] == W[b] and (not v[a]):
						v[a] = True
						b += 1
					a += 1
				if b == len(W):
					res += 1
		return res


class Solution:

	def numberOfSubsequences(self, S, W):
		c = 0
		a = [0 for i in range(len(S))]
		for i in range(len(S)):
			if S[i] == W[0] and a[i] != 1:
				k = 1
				a[i] = 1
				j = i + 1
				while j < len(S) and k < len(W):
					if S[j] == W[k] and a[j] != 1:
						a[j] = 1
						k += 1
					j += 1
				if k == len(W):
					c += 1
				else:
					break
		return c


class Solution:

	def numberOfSubsequences(self, S, W):
		n = len(S)
		m = len(W)
		lst = list(S)
		i = 0
		j = 0
		cnt = 0
		while i < n:
			if lst[i] == W[j]:
				lst[i] = '#'
				j += 1
			i += 1
			if j == m:
				cnt += 1
				i = 0
				j = 0
		return cnt


class Solution:

	def numberOfSubsequences(self, s, w):
		k = set(w)
		p = []
		for i in range(len(s)):
			if s[i] in k:
				p.append(s[i])
		j = 0
		ans = 0
		i = 0
		z = set()
		while i < len(p):
			if p[i] == w[j] and i not in z:
				j = j + 1
				if j == 1:
					m = i
				z.add(i)
			if j == len(w):
				j = 0
				ans = ans + 1
				i = m
			i = i + 1
		return ans


class Solution:

	def numberOfSubsequences(self, S, W):
		l = list(S)
		count = 0
		j = 0
		i = 0
		while i < len(l):
			if j == len(W):
				count += 1
				j = 0
				i = 0
			if l[i] == W[j]:
				l[i] = '@'
				j += 1
			i += 1
		if j == len(W):
			count += 1
		return count


class Solution:

	def numberOfSubsequences(self, S, W):
		S = list(S)
		count = 0
		W = list(W)
		while True:
			i = 0
			j = 0
			flag = False
			while i < len(S):
				if S[i] == W[j]:
					j += 1
					S[i] = '*'
					if j == len(W):
						count += 1
						flag = True
						break
				i += 1
			if not flag:
				break
		return count


class Solution:

	def numberOfSubsequences(self, S, W):
		(flg, count, f) = (1, 0, 0)
		while flg == 1:
			j = 0
			flg = 0
			for i in range(len(S)):
				if S[i] == W[j]:
					S = S[0:i] + ' ' + S[i + 1:]
					j += 1
					if j == len(W):
						count += 1
						j = 0
						flg = 1
						break
			if flg == 0:
				break
		return count


from collections import defaultdict

class Solution:

	def numberOfSubsequences(self, S, W):
		self.base = list(S)
		self.target = W
		self.base_len = len(S)
		self.target_len = len(W)
		max_subs = self.base_len // self.target_len + 1
		if self.target_len > self.base_len or self.target_len == 0 or self.base_len == 0:
			return 0
		self.sequences = {}
		self.sequence_map = defaultdict(lambda : [0, 2])
		self.first = self.target[0]
		for i in range(self.target_len):
			self.sequence_map[self.target[i]].append(0)
		for letter in self.sequence_map:
			self.sequences[letter] = [None] * (self.base_len + 1)
		self.filter()
		idx = 0
		pidx = None
		count = 0
		while True:
			letter = self.target[idx]
			sequence = self.sequences[letter]
			sequence_map = self.sequence_map[letter]
			pidx = self.walk(pidx, sequence_map, sequence)
			if pidx is None:
				return count
			idx += 1
			if idx == self.target_len:
				idx = 0
				count += 1
				pidx = None

	def filter(self):
		for i in range(self.base_len):
			letter = self.base[i]
			if letter in self.sequence_map:
				self.sequences[letter][self.sequence_map[letter][0]] = i
				self.sequence_map[letter][0] += 1

	def walk(self, pidx, sequence_map, sequence):
		star = sequence[sequence_map[sequence_map[1]]]
		while star is not None:
			if star < 0:
				pass
			elif pidx is None or star > pidx:
				sequence[sequence_map[sequence_map[1]]] = -(1 + star)
				self.update_map(sequence_map)
				return star
			sequence_map[sequence_map[1]] += 1
			star = sequence[sequence_map[sequence_map[1]]]
		return None

	def update_map(self, sequence_map):
		current = sequence_map[1]
		nextt = current + 1
		first = 2
		if nextt == len(sequence_map):
			sequence_map[1] = first
			return
		sequence_map[1] = nextt
		sequence_map[nextt] = sequence_map[current]


class Solution:

	def numberOfSubsequences(self, X, Y):
		count = 0
		l = list(S)
		for i in range(len(l)):
			k = 0
			for j in range(i, len(l)):
				if l[j] == W[k]:
					k += 1
					l[j] = ')'
				if k == len(W):
					count += 1
					break
		return count


class Solution:

	def numberOfSubsequences(self, S, W):
		empty = len(set(W))
		indices = {i: [] for i in W}
		for i in range(len(S)):
			letter = S[i]
			if letter in indices:
				if indices[letter] == []:
					empty -= 1
				indices[letter].append(i)
		if empty:
			return 0
		num = 0
		all_num_calc = False
		while not all_num_calc:
			curr_ind = -1
			for i in W:
				j = 0
				while j < len(indices[i]) and indices[i][j] <= curr_ind:
					j += 1
				if j >= len(indices[i]):
					all_num_calc = True
					break
				else:
					curr_ind = indices[i][j]
					indices[i][j] = -1
			else:
				num += 1
		return num


class Solution:

	def numberOfSubsequences(self, S, W):
		count = 0
		l = list(S)
		k = 0
		for i in range(len(S)):
			k = 0
			j = i
			while k < len(W) and j < len(S):
				if l[j] == W[k]:
					k = k + 1
					l[j] = ']'
				j = j + 1
			if k != len(W):
				return count
			count = count + 1
		return count


class Solution:

	def numberOfSubsequences(self, S, W):
		ans = 0
		nS = len(S)
		nW = len(W)
		lS = list(S)
		for i in range(nS):
			k = 0
			for j in range(i, nS):
				if lS[j] == W[k]:
					k += 1
					lS[j] = '0'
				if k == nW:
					ans += 1
					break
		return ans


class Solution:

	def numberOfSubsequences(self, s, w):
		count = 0
		l = set()
		for i in range(len(S)):
			if S[i] == W[0]:
				p = set()
				pp = i
				for j in range(len(W)):
					if W[j] in S[pp:]:
						pp = S.index(W[j], pp, len(S))
						q = S.count(W[j], pp, len(S))
						for i in range(q):
							if pp not in l:
								p.add(pp)
								pp += 1
								break
							elif W[j] in S[pp + 1:]:
								pp = S.index(W[j], pp + 1, len(S))
							else:
								break
					else:
						break
				if len(p) == len(W):
					for i in p:
						l.add(i)
		return len(l) // len(W)


class Solution:

	def numberOfSubsequences(self, S, W):
		indx_map = [[] for __ in range(26)]
		dp = [0] * len(W)
		for i in range(len(W)):
			indx = ord(W[i]) - ord('a')
			indx_map[indx].append(i)
		for i in range(len(S)):
			indx = ord(S[i]) - ord('a')
			if not indx_map[indx]:
				continue
			for j in indx_map[indx][-1::-1]:
				if j == 0:
					dp[j] += 1
					break
				elif dp[j - 1] > dp[j]:
					dp[j] += 1
					break
		return dp[-1]