Find the longest subsequence X of a string A which is a substring Y of a string B.
Note: All letters of the Strings are Uppercased.
 
Example 1: 
Input:
A = "ABCD" , B = "BACDBDCD"
Output:
3
Explanation:
The answer would be 3 as because "ACD"
is the longest subsequence of A which
is also a substring of B.
Example 2:
Input:
A = "A" , B = "A"
Output:
1
Explanation:
The answer would be 1 as because "A"
is the longest subsequence of A which
is also a substring of B. 
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function getLongestSubsequence() which takes Strings A  and B as input and returns the answer.
 
Expected Time Complexity: O(|S|^{2})
Expected Auxiliary Space: O(|S|^{2})
 
Constraints:
1 <= |A|,|B| <= 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def getLongestSubsequence(self, A , B):

        # code here 

Solutions:
class Solution:

	def getLongestSubsequence(self, A, B):
		(na, nb) = (len(A), len(B))
		ans = 0
		for i in range(nb):
			k = i
			temp = 0
			for j in range(na):
				if k < nb and A[j] == B[k]:
					k += 1
					temp += 1
			ans = max(ans, temp)
		return ans


class Solution:

	def getLongestSubsequence(self, A, B):
		(l1, l2) = (len(A), len(B))
		maxlen = float('-inf')
		dp = [[0 for i in range(l2 + 1)] for j in range(l1 + 1)]
		for i in range(1, l1 + 1):
			for j in range(1, l2 + 1):
				if A[i - 1] == B[j - 1]:
					dp[i][j] = max(1 + dp[i - 1][j - 1], dp[i - 1][j])
				else:
					dp[i][j] = dp[i - 1][j]
				maxlen = max(maxlen, dp[i][j])
		return maxlen

	def getLongestSubsequence(self, A, B):
		(l1, l2) = (len(A), len(B))
		ans = 0
		for i in range(l2):
			(k, count) = (i, 0)
			for j in range(l1):
				if k < l2 and B[k] == A[j]:
					(k, count) = (k + 1, count + 1)
			ans = max(ans, count)
		return ans


class Solution:

	def getLongestSubsequence(self, A, B):
		m = len(A)
		n = len(B)
		ans = 0
		for i in range(n):
			ix = -1
			for j in range(i, n):
				ix += 1
				while ix < m and A[ix] != B[j]:
					ix += 1
				if ix == m:
					break
				ans = max(ans, j - i + 1)
		return ans


class Solution:

	def getLongestSubsequence(self, A, B):

		def findChar(ch, src, ix):
			for i in range(ix, len(src)):
				if src[i] == ch:
					return i
			return -1
		ans = 0
		for i in range(len(B)):
			ix = -1
			for j in range(i, len(B)):
				ix = findChar(B[j], A, ix + 1)
				if ix == -1:
					break
				ans = max(ans, j - i + 1)
		return ans