Given two strings a and b. Check whether they contain any common subsequence (non empty) or not.
Example 1:
Input:
a = "ABEF" b = "CADE"
Output: 1
Explanation: Subsequence "AE" occurs
in both the strings.
Ã¢â¬â¹Example 2:
Input: 
a = "ABCD", b = "EFGH"
Output: 0
Explanation: There's no common subsequence
in both the strings.
Your Task:
You don't need to read input or print anything. Your task is to complete the function commonSubseq() which takes the string a and string b as inputs and returns true if there's a common subsequence in both the strings. Else, it returns false.
Expected Time Complexity: O(|a| + |b|).
Expected Auxiliary Space: O(1).
Constraints:
2 <= |a|, |b| <=10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3
class Solution:
	def commonSubseq(self, a, b):
		# your code here

Solutions:
class Solution:

	def commonSubseq(self, a, b):
		for i in a:
			if i in b:
				return 1
		return 0


from collections import defaultdict

class Solution:

	def commonSubseq(self, a, b):
		hmap = defaultdict(int)
		for i in range(0, len(a)):
			if a[i] not in hmap:
				hmap[a[i]] = 1
			else:
				hmap[a[i]] += 1
		for i in range(0, len(b)):
			if b[i] in hmap:
				return True
		return False


class Solution:

	def commonSubseq(self, a, b):
		p = len(a)
		i = 0
		while i < p:
			if a[i] in b:
				return 1
			i = i + 1
		return 0


class Solution:

	def commonSubseq(self, a, b):
		for i in range(len(a)):
			if a[i] in b:
				return True
		return False


class Solution:

	def commonSubseq(self, a, b):
		x = len(a)
		y = len(b)
		flag = 0
		for i in a:
			if i in b:
				flag = 1
				break
			else:
				continue
		return flag


class Solution:

	def commonSubseq(self, a, b):
		c = 0
		for i in range(len(a)):
			if a[i] in b:
				c += 1
		if c > 0:
			return True
		else:
			return False


class Solution:

	def commonSubseq(self, a, b):
		if a == '' or b == '':
			return 0
		c = 0
		list(a)
		list(b)
		for i in a:
			if i in b:
				c = c + 1
		if c == 0:
			return 0
		else:
			return 1


class Solution:

	def commonSubseq(self, a, b):
		return 1 if len(set(list(a)).intersection(list(b))) >= 1 else 0


class Solution:

	def commonSubseq(self, a, b):
		a = set(a)
		b = set(b)
		s = ''
		for i in a:
			s += i
		for i in b:
			s += i
		d = {}
		for i in s:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		z = ''
		for i in d:
			if d[i] > 1:
				z += i
		if z:
			return True
		else:
			return False


class Solution:

	def commonSubseq(self, a, b):
		return any([item in b for item in a])


class Solution:

	def commonSubseq(self, a, b):
		for letter in a:
			if letter in b:
				return True
		return False


class Solution:

	def commonSubseq(self, a, b):
		dic = {}
		for i in range(len(a)):
			dic[a[i]] = 1 + dic.get(a[i], 0)
		for i in range(len(b)):
			if b[i] in dic:
				return 1
		return 0


class Solution:

	def commonSubseq(self, a, b):
		s = set(a)
		for i in b:
			if i in s:
				return True
		return False


class Solution:

	def commonSubseq(self, a, b):
		a = set(a)
		b = set(b)
		ans = a.intersection(b)
		if len(ans) == 0:
			return False
		else:
			ans = sorted(ans)
			ans = ''.join(ans)
			return True


class Solution:

	def commonSubseq(self, a, b):
		d = {}
		for i in a:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for i in b:
			if i in d:
				if d[i] > 0:
					d[i] -= 1
		su = sum([i for i in d.values()])
		return len(a) - su


class Solution:

	def commonSubseq(self, a, b):
		lst = []
		for i in a:
			if i in b and i not in lst:
				return 1
			else:
				lst.append(i)
		return 0


class Solution:

	def commonSubseq(self, a, b):
		c = set(a) & set(b)
		if len(c) > 0:
			return 1
		else:
			return 0


class Solution:

	def commonSubseq(self, a, b):
		c = 0
		l1 = list(a)
		for i in l1:
			if i not in b:
				c += 1
		if len(b) == c:
			return False
		else:
			return True


class Solution:

	def commonSubseq(self, a, b):
		for i in range(0, len(a)):
			for j in range(0, len(b)):
				if a[i] == b[j]:
					return 1


class Solution:

	def commonSubseq(self, a, b):
		x = {}
		for i in b:
			if i in x:
				x[i] += 1
			else:
				x[i] = 1
		for i in a:
			if i in x:
				return True
		return False


class Solution:

	def commonSubseq(self, a, b):
		if len(set(a).intersection(set(b))) > 0:
			return True
		else:
			return False


class Solution:

	def commonSubseq(self, a, b):
		d = {}
		for x in a:
			if x not in d:
				d[x] = 1
		for x in b:
			if x in d:
				return 1
		return 0


class Solution:

	def commonSubseq(self, a, b):
		d = {}
		for i in a:
			if i not in d:
				d[i] = 1
		for i in b:
			if i in d:
				return True
		return False


class Solution:

	def commonSubseq(self, a, b):
		(n1, n2) = (len(a), len(b))
		for i in range(n1):
			for j in range(n2):
				if a[i] == b[j]:
					return True
		return False


class Solution:

	def commonSubseq(self, a, b):
		(S1, S2) = (a, b)
		smaller_set = set()
		if len(S1) <= len(S2):
			smaller_string = S1
			larger_string = S2
		else:
			smaller_string = S2
			larger_string = S1
		for i in range(len(smaller_string)):
			smaller_set.add(smaller_string[i])
		for i in range(len(larger_string)):
			if larger_string[i] in smaller_set:
				return 1
		return 0
if __name__ == '__main__':
	t = int(input())
	for tc in range(t):
		(a, b) = input().split()
		ob = Solution()
		if ob.commonSubseq(a, b):
			print(1)
		else:
			print(0)


class Solution:

	def commonSubseq(self, a, b):
		for i in a:
			if i in b:
				return True
		for i in b:
			if i in a:
				return True
		return False
if __name__ == '__main__':
	t = int(input())
	for tc in range(t):
		(a, b) = input().split()
		ob = Solution()
		if ob.commonSubseq(a, b):
			print(1)
		else:
			print(0)


class Solution:

	def commonSubseq(self, a, b):
		li1 = [0] * 122
		li2 = [0] * 122
		for i in range(len(a)):
			li1[ord(a[i])] += 1
		for i in range(len(b)):
			li2[ord(b[i])] += 1
		for i in range(len(li1)):
			if li1[i] > 0 and li2[i] > 0:
				return 1
		else:
			return 0
if __name__ == '__main__':
	t = int(input())
	for tc in range(t):
		(a, b) = input().split()
		ob = Solution()
		if ob.commonSubseq(a, b):
			print(1)
		else:
			print(0)


class Solution:

	def commonSubseq(self, a, b):
		x = set(a)
		y = set(b)
		k = x & y
		if len(k) > 0:
			return 1
		return 0
if __name__ == '__main__':
	t = int(input())
	for tc in range(t):
		(a, b) = input().split()
		ob = Solution()
		if ob.commonSubseq(a, b):
			print(1)
		else:
			print(0)


class Solution:

	def commonSubseq(self, a, b):
		a = set(a)
		b = set(b)
		c = set()
		c = a.intersection(b)
		if len(c) == 0:
			return 0
		else:
			return 1
if __name__ == '__main__':
	t = int(input())
	for tc in range(t):
		(a, b) = input().split()
		ob = Solution()
		if ob.commonSubseq(a, b):
			print(1)
		else:
			print(0)


class Solution:

	def commonSubseq(self, a, b):
		subStr = []
		for i in range(len(a)):
			if b.find(a[i]) != -1:
				subStr.append(a[i])
		return 1 if len(subStr) > 0 else 0


class Solution:

	def commonSubseq(self, a, b):
		for i in a:
			if i in b:
				return True
				break
		return False


class Solution:

	def commonSubseq(self, a, b):
		count = 0
		for i in a:
			if i in b:
				count += 1
		if count > 0:
			return True
		else:
			return False


class Solution:

	def commonSubseq(self, a, b):
		char_count = [False] * 26
		for char in a:
			index = ord(char) - ord('A')
			char_count[index] = True
		for char in b:
			index = ord(char) - ord('A')
			if char_count[index]:
				return True
		return False


class Solution:

	def commonSubseq(self, a, b):
		l = [0] * 26
		ll = [0] * 26
		for i in a:
			l[ord(i) - ord('A')] += 1
		for i in b:
			ll[ord(i) - ord('A')] += 1
		s1 = ''
		s = ''
		for i in b:
			if l[ord(i) - ord('A')] > 0:
				s += i
				l[ord(i) - ord('A')] -= 1
		for i in a:
			if ll[ord(i) - ord('A')] > 0:
				s1 += i
				ll[ord(i) - ord('A')] -= 1
		if len(s) != 0:
			return 1
		return 0


class Solution:

	def commonSubseq(self, a, b):
		count = 0
		for x in a:
			if x in b:
				count += 1
		if count == 0:
			return False
		return True


class Solution:

	def commonSubseq(self, a, b):
		k = ''
		for i in a:
			if i in b:
				k += i
		if len(k) >= 1:
			return True
		return False


class Solution:

	def commonSubseq(self, a, b):
		if len(set(a) & set(b)) >= 1:
			return True
		return False


class Solution:

	def commonSubseq(self, a, b):
		seen = set(a)
		for c in b:
			if c in seen:
				return True
		return False


class Solution:

	def commonSubseq(self, a, b):
		memo = {}
		for i in range(len(a)):
			memo[a[i]] = memo.get(a[i], 0) + 1
		for i in range(len(b)):
			if memo.get(b[i]):
				return True
		return False


class Solution:

	def commonSubseq(self, a, b):
		x = -1
		for i in range(len(a)):
			x = b.find(a[i])
			if x != -1:
				return 1
		return 0


class Solution:

	def commonSubseq(self, a, b):
		if set(a).intersection(set(b)):
			return True
		return False