Given 3 strings A, B and C, the task is to find the longest common sub-sequence in all three given sequences.
Example 1:
Input:
A = "geeks", B = "geeksfor", 
C = "geeksforgeeks"
Output: 5
Explanation: "geeks"is the longest common
subsequence with length 5.
Ã¢â¬â¹Example 2:
Input: 
A = "abcd", B = "efgh", C = "ijkl"
Output: 0
Explanation: There's no common subsequence
in all the strings.
Your Task:
You don't need to read input or print anything. Your task is to complete the function LCSof3() which takes the strings A, B, C and their lengths n1, n2, n3 as input and returns the length of the longest common subsequence in all the 3 strings.
Expected Time Complexity: O(n1*n2*n3).
Expected Auxiliary Space: O(n1*n2*n3).
Constraints:
1<=n1, n2, n3<=20

Difficulty: MEDIUM
Tags: String algorithms

Dynamic programming

Data structures
Skill types: Dynamic programming

Data structures
Expected Time Complexity: O(n1*n2*n3).
Expected Auxiliary Space: O(n1*n2*n3).

Starter code:
#User function Template for python3

class Solution:

    def LCSof3(self,A,B,C,n1,n2,n3):
        # code here

Solutions:
class Solution:

	def LCSof3(self, A, B, C, n1, n2, n3):
		dp = [[[0 for k in range(len(C) + 1)] for j in range(len(B) + 1)] for i in range(len(A) + 1)]
		str1 = ''
		for i in range(1, len(A) + 1):
			for j in range(1, len(B) + 1):
				for k in range(1, len(C) + 1):
					if A[i - 1] == B[j - 1] == C[k - 1]:
						dp[i][j][k] = 1 + dp[i - 1][j - 1][k - 1]
					elif i == 0 and j == 0 and (k == 0):
						dp[i][j][k] = 0
					else:
						dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j - 1][k], dp[i][j][k - 1])
		return dp[-1][-1][-1]


class Solution:

	def LCSof3(self, a, b, c, n1, n2, n3):
		n1 = len(a)
		n2 = len(b)
		n3 = len(c)
		dp = [[[0 for _ in range(n3 + 1)] for _ in range(n2 + 1)] for _ in range(n1 + 1)]
		for i in range(1, n1 + 1):
			for j in range(1, n2 + 1):
				for k in range(1, n3 + 1):
					if a[i - 1] == b[j - 1] == c[k - 1]:
						dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1
					else:
						dp[i][j][k] = max(dp[i - 1][j][k], max(dp[i][j - 1][k], dp[i][j][k - 1]))
		return dp[n1][n2][n3]


class Solution:

	def fun(self, a, b, c, i, j, k, dp):
		if i == 0 or j == 0 or k == 0:
			return 0
		if dp[i][j][k] != -1:
			return dp[i][j][k]
		if a[i - 1] == b[j - 1] and a[i - 1] == c[k - 1]:
			dp[i][j][k] = 1 + self.fun(a, b, c, i - 1, j - 1, k - 1, dp)
			return dp[i][j][k]
		else:
			dp[i][j][k] = 0 + max(self.fun(a, b, c, i - 1, j, k, dp), self.fun(a, b, c, i, j - 1, k, dp), self.fun(a, b, c, i, j, k - 1, dp))
			return dp[i][j][k]

	def LCSof3(self, A, B, C, n1, n2, n3):
		dp = [[[0 for i in range(n3 + 1)] for j in range(n2 + 1)] for k in range(n1 + 1)]
		for i in range(1, n1 + 1):
			for j in range(1, n2 + 1):
				for k in range(1, n3 + 1):
					if A[i - 1] == B[j - 1] and A[i - 1] == C[k - 1]:
						dp[i][j][k] = 1 + dp[i - 1][j - 1][k - 1]
					else:
						dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j - 1][k], dp[i][j][k - 1])
		return dp[n1][n2][n3]


import numpy as np

class Solution:

	def rec_sol(self, A, B, C, n1, n2, n3):
		if n1 == 0 or n2 == 0 or n3 == 0:
			return 0
		if A[n1 - 1] == B[n2 - 1] and B[n2 - 1] == C[n3 - 1]:
			return 1 + self.rec_sol(A, B, C, n1 - 1, n2 - 1, n3 - 1)
		return max(max(self.rec_sol(A, B, C, n1 - 1, n2, n3), self.rec_sol(A, B, C, n1, n2 - 1, n3)), self.rec_sol(A, B, C, n1, n2, n3 - 1))

	def dp_sol(self, A, B, C, n1, n2, n3):
		dp = np.zeros((n1 + 1, n2 + 1, n3 + 1))
		for i in range(n1):
			for j in range(n2):
				for k in range(n3):
					if A[i] == B[j] and B[j] == C[k]:
						dp[i + 1][j + 1][k + 1] = 1 + dp[i][j][k]
					else:
						dp[i + 1][j + 1][k + 1] = max(max(dp[i][j + 1][k + 1], dp[i + 1][j][k + 1]), dp[i + 1][j + 1][k])
		return int(dp[n1][n2][n3])

	def LCSof3(self, A, B, C, n1, n2, n3):
		return self.dp_sol(A, B, C, n1, n2, n3)


class Solution:

	def LCSof3(self, A, B, C, n1, n2, n3):
		dp = [[[0 for h in range(n1 + 1)] for g in range(n2 + 1)] for c in range(n3 + 1)]
		for h in range(1, n3 + 1):
			for g in range(1, n2 + 1):
				for c in range(1, n1 + 1):
					if A[c - 1] == B[g - 1] and B[g - 1] == C[h - 1]:
						dp[h][g][c] = 1 + dp[h - 1][g - 1][c - 1]
					else:
						dp[h][g][c] = max(dp[h - 1][g][c], dp[h][g - 1][c], dp[h][g][c - 1], dp[h - 1][g - 1][c], dp[h][g - 1][c - 1], dp[h - 1][g][c - 1])
		return dp[n3][n2][n1]


class Solution:

	def LCSof3(self, A, B, C, n1, n2, n3):
		return self.solveTab(A, B, C)

	def solveTab(self, a, b, c):
		dp = [[[0 for i in range(len(C) + 1)] for j in range(len(B) + 1)] for k in range(len(A) + 1)]
		ans = 0
		for i in range(len(a) - 1, -1, -1):
			for j in range(len(b) - 1, -1, -1):
				for k in range(len(c) - 1, -1, -1):
					if a[i] == b[j] == c[k]:
						ans = 1 + dp[i + 1][j + 1][k + 1]
					else:
						ans = max(dp[i + 1][j][k], dp[i][j + 1][k], dp[i][j][k + 1], dp[i + 1][j + 1][k], dp[i + 1][j][k + 1], dp[i][j + 1][k + 1])
					dp[i][j][k] = ans
		return dp[0][0][0]

	def solve(self, a, b, c, i, j, k, dp):
		if i == len(a):
			return 0
		if j == len(b):
			return 0
		if k == len(c):
			return 0
		ans = 0
		if dp[i][j][k] != -1:
			return dp[i][j][k]
		if a[i] == b[j] == c[k]:
			ans = 1 + self.solve(a, b, c, i + 1, j + 1, k + 1, dp)
		else:
			ans = max(self.solve(a, b, c, i + 1, j, k, dp), self.solve(a, b, c, i, j + 1, k, dp), self.solve(a, b, c, i, j, k + 1, dp), self.solve(a, b, c, i + 1, j + 1, k, dp), self.solve(a, b, c, i, j + 1, k + 1, dp), self.solve(a, b, c, i + 1, j, k + 1, dp))
		dp[i][j][k] = ans
		return dp[i][j][k]


class Solution:

	def LCSof3(self, A, B, C, n1, n2, n3):
		stateMap = [[[0 for _ in range(n3 + 1)] for u in range(n2 + 1)] for _ in range(n1 + 1)]
		for a in range(1, n1 + 1):
			for b in range(1, n2 + 1):
				for c in range(1, n3 + 1):
					if A[a - 1] == B[b - 1] and B[b - 1] == C[c - 1]:
						stateMap[a][b][c] = 1 + stateMap[a - 1][b - 1][c - 1]
					else:
						stateMap[a][b][c] = max(stateMap[a - 1][b][c], stateMap[a][b - 1][c], stateMap[a][b][c - 1])
		return stateMap[n1][n2][n3]


import sys

class Solution:

	def LCSof3(self, s1, s2, s3, x, y, z):
		sys.setrecursionlimit(1000)
		dp = [[[-1] * y for i in range(x)] for i in range(z)]

		def findlcs(i, j, k, x, y, z, s1, s2, s3):
			if i < 0 or i >= x or j < 0 or (j >= y) or (k < 0) or (k >= z):
				return 0
			if dp[k][i][j] != -1:
				return dp[k][i][j]
			val = 0
			if s1[i] == s2[j] and s2[j] == s3[k]:
				val = 1 + findlcs(i + 1, j + 1, k + 1, x, y, z, s1, s2, s3)
			val = max(val, findlcs(i + 1, j, k, x, y, z, s1, s2, s3))
			val = max(val, findlcs(i, j + 1, k, x, y, z, s1, s2, s3))
			val = max(val, findlcs(i, j, k + 1, x, y, z, s1, s2, s3))
			val = max(val, findlcs(i + 1, j + 1, k, x, y, z, s1, s2, s3))
			val = max(val, findlcs(i, j + 1, k + 1, x, y, z, s1, s2, s3))
			val = max(val, findlcs(i + 1, j, k + 1, x, y, z, s1, s2, s3))
			dp[k][i][j] = val
			return val
		return findlcs(0, 0, 0, x, y, z, s1, s2, s3)


class Solution:

	def LCSof3(self, A, B, C, n1, n2, n3):
		t = [[[0 for _ in range(n3 + 1)] for _ in range(n2 + 1)] for _ in range(n1 + 1)]
		for i in range(1, n1 + 1):
			for j in range(1, n2 + 1):
				for k in range(1, n3 + 1):
					if A[i - 1] == B[j - 1] and A[i - 1] == C[k - 1]:
						t[i][j][k] = 1 + t[i - 1][j - 1][k - 1]
					else:
						t[i][j][k] = max(t[i - 1][j][k], t[i][j - 1][k], t[i][j][k - 1])
		return t[n1][n2][n3]


class Solution:

	def solve(self, i, j, k, s1, s2, s3, dp):
		if i >= len(s1) or j >= len(s2) or k >= len(s3):
			return 0
		if s1[i] == s2[j] and s2[j] == s3[k]:
			return 1 + self.solve(i + 1, j + 1, k + 1, s1, s2, s3, dp)
		if dp[i][j][k] != -1:
			return dp[i][j][k]
		else:
			dp[i][j][k] = max(self.solve(i + 1, j, k, s1, s2, s3, dp), max(self.solve(i, j + 1, k, s1, s2, s3, dp), self.solve(i, j, k + 1, s1, s2, s3, dp)))
			return dp[i][j][k]

	def LCSof3(self, A, B, C, n1, n2, n3):
		dp = [[[-1 for i in range(n3 + 1)] for j in range(n2 + 1)] for k in range(n1 + 1)]
		return self.solve(0, 0, 0, A, B, C, dp)


class Solution:

	def LCSof3(self, A, B, C, n1, n2, n3):

		def lcs(i, j, k, A, B, C, dp):
			if i >= len(A) or j >= len(B) or k >= len(C):
				return 0
			if dp[i][j][k] != -1:
				return dp[i][j][k]
			if A[i] == B[j] and A[i] == C[k]:
				x = 1 + lcs(i + 1, j + 1, k + 1, A, B, C, dp)
				dp[i][j][k] = x
				return x
			elif A[i] != B[j] or B[j] != C[k] or C[k] != A[i]:
				t1 = lcs(i + 1, j, k, A, B, C, dp)
				t2 = lcs(i, j + 1, k, A, B, C, dp)
				t3 = lcs(i, j, k + 1, A, B, C, dp)
				dp[i][j][k] = max(t1, t2, t3)
				return max(t1, t2, t3)
		dp = [[[-1] * len(C) for _ in range(len(B))] for _ in range(len(A))]
		return lcs(0, 0, 0, A, B, C, dp)


class Solution:

	def LCSof3(self, A, B, C, m, n, o):
		(m, n, o) = (len(A), len(B), len(C))
		dp = [[[0 for _ in range(o + 1)] for _ in range(n + 1)] for _ in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				for k in range(1, o + 1):
					if A[i - 1] == B[j - 1] == C[k - 1]:
						dp[i][j][k] = 1 + dp[i - 1][j - 1][k - 1]
					else:
						dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j - 1][k], dp[i][j][k - 1])
		return dp[m][n][o]


class Solution:

	def LCSof3(self, A, B, C, n1, n2, n3):
		Dp = [[[0 for i in range(n3 + 3)] for j in range(n2 + 2)] for k in range(n1 + 1)]
		for i in range(n1 + 1):
			for j in range(n2 + 1):
				for k in range(n3 + 1):
					if i == 0 or j == 0 or k == 0:
						Dp[i][j][k] = 0
					elif A[i - 1] == B[j - 1] and B[j - 1] == C[k - 1]:
						Dp[i][j][k] = 1 + Dp[i - 1][j - 1][k - 1]
					else:
						Dp[i][j][k] = max([Dp[i - 1][j][k], Dp[i][j - 1][k], Dp[i][j][k - 1]])
		return Dp[n1][n2][n3]


class Solution:

	def LCSof3(self, A, B, C, n1, n2, n3):
		dp = {}

		def fun(i, j, k):
			if i == 0 or j == 0 or k == 0:
				return 0
			if (i, j, k) in dp:
				return dp[i, j, k]
			if A[i - 1] == B[j - 1] and B[j - 1] == C[k - 1]:
				return 1 + fun(i - 1, j - 1, k - 1)
			dp[i, j, k] = max(fun(i - 1, j, k), fun(i, j - 1, k), fun(i, j, k - 1))
			return dp[i, j, k]
		return fun(n1, n2, n3)


class Solution:

	def LCSof3(self, A, B, C, n1, n2, n3):

		def manu(x, y, z, i, j, k):
			if i == len(x) or j == len(y) or k == len(z):
				return 0
			if dp[i][j][k] != -1:
				return dp[i][j][k]
			if x[i] == y[j] and y[j] == z[k]:
				f = 1 + manu(x, y, z, i + 1, j + 1, k + 1)
			else:
				f = max(manu(x, y, z, i + 1, j, k), manu(x, y, z, i, j + 1, k), manu(x, y, z, i, j, k + 1), manu(x, y, z, i + 1, j + 1, k), manu(x, y, z, i + 1, j, k + 1), manu(x, y, z, i, j + 1, k + 1))
			dp[i][j][k] = f
			return f
		dp = [[[-1 for i in range(len(C))] for i in range(len(B))] for i in range(len(A))]
		return manu(A, B, C, 0, 0, 0)


import sys
sys.setrecursionlimit(10 ** 5)

class Solution:

	def LCSof3(self, A, B, C, n1, n2, n3):

		def _solve(i1, i2, i3):
			if i1 >= n1 or i2 >= n2 or i3 >= n3:
				return 0
			if dp[i1][i2][i3] >= 0:
				return dp[i1][i2][i3]
			if A[i1] == B[i2] == C[i3]:
				ans = dp[i1][i2][i3] = 1 + _solve(i1 + 1, i2 + 1, i3 + 1)
			else:
				ans = dp[i1][i2][i3] = max(_solve(i1 + 1, i2, i3), _solve(i1, i2 + 1, i3), _solve(i1, i2, i3 + 1))
			return ans
		dp = [[[-1] * n3 for _ in range(n2)] for _ in range(n1)]
		ans = _solve(0, 0, 0)
		return ans


from functools import lru_cache

class Solution:

	def LCSof3(self, s1, s2, s3, l, m, n):

		@lru_cache(None)
		def fun(s1, s2, s3, l, m, n):
			if l == 0 or m == 0 or n == 0:
				return 0
			if s1[l - 1] == s2[m - 1] == s3[n - 1]:
				return 1 + fun(s1, s2, s3, l - 1, m - 1, n - 1)
			opt1 = fun(s1, s2, s3, l - 1, m, n)
			opt2 = fun(s1, s2, s3, l, m - 1, n)
			opt3 = fun(s1, s2, s3, l, m, n - 1)
			return max(opt1, opt2, opt3)
		return fun(s1, s2, s3, l, m, n)


class Solution:

	def LCSof3(self, s1, s2, s3, n1, n2, n3):
		dp = [[[0 for k in range(n3 + 1)] for j in range(n2 + 1)] for i in range(n1 + 1)]
		for i in range(1, n1 + 1):
			for j in range(1, n2 + 1):
				for k in range(1, n3 + 1):
					if s1[i - 1] == s2[j - 1] == s3[k - 1]:
						dp[i][j][k] = 1 + dp[i - 1][j - 1][k - 1]
					else:
						dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j - 1][k], dp[i][j][k - 1])
		return dp[n1][n2][n3]


class Solution:

	def LCSof3(self, A, B, C, n1, n2, n3):
		return self.helper(A, B, C, 0, {})

	def helper(self, word1, word2, word3, output, store):
		if not word1 or not word2 or (not word3):
			return output
		if (word1, word2, word3) in store:
			return output + store[word1, word2, word3]
		if word1[0] == word2[0] == word3[0]:
			maxi = self.helper(word1[1:], word2[1:], word3[1:], output + 1, store)
		else:
			first = self.helper(word1[1:], word2, word3, output, store)
			second = self.helper(word1, word2[1:], word3, output, store)
			third = self.helper(word1, word2, word3[1:], output, store)
			maxi = max(first, second, third)
		store[word1, word2, word3] = maxi - output
		return maxi


class Solution:

	def LCSof3(self, A, B, C, n1, n2, n3):
		dp = [[[0 for z in range(n3 + 1)] for x in range(n2 + 1)] for y in range(n1 + 1)]
		for i in range(n1 + 1):
			for j in range(n2 + 1):
				for k in range(n3 + 1):
					if i == 0 or j == 0 or k == 0:
						dp[i][j][k] = 0
					elif A[i - 1] == B[j - 1] == C[k - 1]:
						dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1
					else:
						dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j - 1][k], dp[i][j][k - 1])
		return dp[n1][n2][n3]


class Solution:

	def LCSof3(self, A, B, C, n1, n2, n3):
		dp = [[[-1 for i in range(n1 + 1)] for i in range(n2 + 1)] for i in range(n3 + 1)]

		def recursive(n1, n2, n3):
			nonlocal A, B, C
			if n1 == 0 or n2 == 0 or n3 == 0:
				return 0
			if dp[n3][n2][n1] != -1:
				return dp[n3][n2][n1]
			if A[n1 - 1] == B[n2 - 1] and B[n2 - 1] == C[n3 - 1]:
				dp[n3][n2][n1] = 1 + recursive(n1 - 1, n2 - 1, n3 - 1)
			else:
				op1 = recursive(n1 - 1, n2, n3)
				op2 = recursive(n1, n2 - 1, n3)
				op3 = recursive(n1, n2, n3 - 1)
				dp[n3][n2][n1] = max(op1, max(op2, op3))
			return dp[n3][n2][n1]
		return recursive(n1, n2, n3)


class Solution:

	def LCSof3(self, a, b, c, n1, n2, n3):
		dp = [[[0 for i in range(n3 + 1)] for j in range(n2 + 1)] for k in range(n1 + 1)]
		for i in range(n1 + 1):
			for j in range(n2 + 1):
				for k in range(n3 + 1):
					if i == 0 or j == 0 or k == 0:
						dp[i][j][k] = 0
					elif a[i - 1] == b[j - 1] and b[j - 1] == c[k - 1]:
						dp[i][j][k] = 1 + dp[i - 1][j - 1][k - 1]
					else:
						dp[i][j][k] = max(max(dp[i - 1][j][k], dp[i][j - 1][k]), dp[i][j][k - 1])
		return dp[n1][n2][n3]


class Solution:

	def LCSof3(self, A, B, C, X, Y, Z):
		table = [[[-1 for i in range(Z + 1)] for _ in range(Y + 1)] for j in range(X + 1)]

		def LCS(X, Y, Z, a, b, c):
			if a == 0 or b == 0 or c == 0:
				return 0
			if table[a][b][c] == -1:
				if X[a - 1] == Y[b - 1] == Z[c - 1]:
					table[a][b][c] = 1 + LCS(X, Y, Z, a - 1, b - 1, c - 1)
				elif X[a - 1] == Y[b - 1] and X[a - 1] != Z[c - 1]:
					table[a][b][c] = max(LCS(X, Y, Z, a - 1, b - 1, c), LCS(X, Y, Z, a, b, c - 1))
				elif X[a - 1] == Z[c - 1] and X[a - 1] != Y[b - 1]:
					table[a][b][c] = max(LCS(X, Y, Z, a - 1, b, c - 1), LCS(X, Y, Z, a, b - 1, c))
				elif Y[b - 1] == Z[c - 1] and X[a - 1] != Y[b - 1]:
					table[a][b][c] = max(LCS(X, Y, Z, a - 1, b, c), LCS(X, Y, Z, a, b - 1, c - 1))
				else:
					table[a][b][c] = max(LCS(X, Y, Z, a - 1, b, c), LCS(X, Y, Z, a, b - 1, c), LCS(X, Y, Z, a, b, c - 1))
			return table[a][b][c]
		return LCS(A, B, C, X, Y, Z)


class Solution:

	def LCSof3(self, A, B, C, n1, n2, n3):
		a = [[[0 for hm in range(n1 + 1)] for gm in range(n2 + 1)] for km in range(n3 + 1)]
		for hm in range(n3 - 1, -1, -1):
			for gm in range(n2 - 1, -1, -1):
				for km in range(n1 - 1, -1, -1):
					if C[hm] == B[gm] and B[gm] == A[km]:
						a[hm][gm][km] = max(1 + a[hm + 1][gm + 1][km + 1], a[hm + 1][gm][km], a[hm][gm + 1][km], a[hm][gm][km + 1], a[hm + 1][gm + 1][km], a[hm + 1][gm][km + 1], a[hm][gm + 1][km + 1])
					else:
						a[hm][gm][km] = max(a[hm + 1][gm][km], a[hm][gm + 1][km], a[hm][gm][km + 1], a[hm + 1][gm + 1][km], a[hm + 1][gm][km + 1], a[hm][gm + 1][km + 1])
		return a[0][0][0]


class Solution:

	def LCSof3(self, A, B, C, n1, n2, n3):
		dp = {}

		def fun(n, m, l):
			if n < 0 or m < 0 or l < 0:
				return 0
			if (n, m, l) in dp:
				return dp[n, m, l]
			if A[n] == B[m] == C[l]:
				dp[n, m, l] = 1 + fun(n - 1, m - 1, l - 1)
			elif A[n] == B[m]:
				dp[n, m, l] = max(fun(n - 1, m - 1, l), fun(n, m, l - 1))
			elif A[n] == C[l]:
				dp[n, m, l] = max(fun(n - 1, m, l - 1), fun(n, m - 1, l))
			elif B[m] == C[l]:
				dp[n, m, l] = max(fun(n, m - 1, l - 1), fun(n - 1, m, l))
			else:
				dp[n, m, l] = max(fun(n - 1, m, l), fun(n, m - 1, l), fun(n, m, l - 1))
			return dp[n, m, l]
		return fun(n1 - 1, n2 - 1, n3 - 1)


def solver(s1, s2, s3, i, j, k, dct):
	if (i, j, k) in dct:
		return dct[i, j, k]
	if i <= -1 or j <= -1 or k <= -1:
		return 0
	res = 0
	if s1[i] == s2[j] and s1[i] == s3[k]:
		res = 1 + solver(s1, s2, s3, i - 1, j - 1, k - 1, dct)
	else:
		res = max(solver(s1, s2, s3, i - 1, j, k, dct), solver(s1, s2, s3, i, j - 1, k, dct), solver(s1, s2, s3, i, j, k - 1, dct))
	dct[i, j, k] = res
	return res

class Solution:

	def LCSof3(self, A, B, C, n1, n2, n3):
		dct = dict()
		return solver(A, B, C, n1 - 1, n2 - 1, n3 - 1, dct)


def solve(a, b, c, i, j, k, dp):
	if i == len(a) or j == len(b) or k == len(c):
		return 0
	if dp[i][j][k] != -1:
		return dp[i][j][k]
	if a[i] == b[j] == c[k]:
		dp[i][j][k] = 1 + solve(a, b, c, i + 1, j + 1, k + 1, dp)
	else:
		op1 = solve(a, b, c, i + 1, j, k, dp)
		op2 = solve(a, b, c, i, j + 1, k, dp)
		op3 = solve(a, b, c, i, j, k + 1, dp)
		dp[i][j][k] = max(op1, op2, op3)
	return dp[i][j][k]

class Solution:

	def LCSof3(self, a, b, c, n1, n2, n3):
		dp = [[[-1 for _ in range(n3)] for _ in range(n2)] for _ in range(n1)]
		return solve(a, b, c, 0, 0, 0, dp)


from collections import defaultdict

class Solution:

	def LCSof3(self, A, B, C, n1, n2, n3):
		hmap = defaultdict(int)

		def rec(i, j, k):
			if (i, j, k) in hmap:
				return hmap[i, j, k]
			if i == n1 or j == n2 or k == n3:
				return 0
			if A[i] == B[j] == C[k]:
				hmap[i, j, k] = 1 + rec(i + 1, j + 1, k + 1)
			else:
				hmap[i, j, k] = max(rec(i + 1, j, k), rec(i, j + 1, k), rec(i, j, k + 1))
			return hmap[i, j, k]
		return rec(0, 0, 0)


from collections import defaultdict

class Solution:

	def LCSof3(self, a, b, c, n1, n2, n3):
		hmap = defaultdict(int)

		def rec(i, j, k):
			if (i, j, k) in hmap:
				return hmap[i, j, k]
			if i == n1 or j == n2 or k == n3:
				return 0
			if a[i] == b[j] == c[k]:
				hmap[i, j, k] = 1 + rec(i + 1, j + 1, k + 1)
			else:
				hmap[i, j, k] = max(rec(i + 1, j, k), rec(i, j + 1, k), rec(i, j, k + 1))
			return hmap[i, j, k]
		return rec(0, 0, 0)


class Solution:

	def solve(self, i, j, k, s1, s2, s3, x, y, z, dp):
		if i >= x or j >= y or k >= z:
			return 0
		if dp[i][j][k] != -1:
			return dp[i][j][k]
		ans = -1000000000.0
		if s1[i] == s2[j] == s3[k]:
			ans = 1 + self.solve(i + 1, j + 1, k + 1, s1, s2, s3, x, y, z, dp)
		else:
			ans = max(self.solve(i + 1, j, k, s1, s2, s3, x, y, z, dp), self.solve(i, j + 1, k, s1, s2, s3, x, y, z, dp), self.solve(i, j, k + 1, s1, s2, s3, x, y, z, dp))
		dp[i][j][k] = ans
		return dp[i][j][k]

	def tabular(self, s1, s2, s3, x, y, z):
		dp = [[[0 for i in range(n3 + 1)] for j in range(n2 + 1)] for k in range(n1 + 1)]
		for i in range(x - 1, -1, -1):
			for j in range(y - 1, -1, -1):
				for k in range(z - 1, -1, -1):
					ans = -1000000000.0
					if s1[i] == s2[j] == s3[k]:
						ans = 1 + dp[i + 1][j + 1][k + 1]
					else:
						ans = max(dp[i + 1][j][k], dp[i][j + 1][k], dp[i][j][k + 1])
					dp[i][j][k] = ans
		return dp[0][0][0]

	def LCSof3(self, A, B, C, n1, n2, n3):
		return self.tabular(A, B, C, n1, n2, n3)


class Solution:

	def LCSof3(self, A, B, C, n1, n2, n3):
		dp = [[[-1 for i in range(n3 + 1)] for j in range(n2 + 1)] for k in range(n1 + 1)]

		def helper(A, B, C, i, j, k, n1, n2, n3, dp):
			if i == n1 or j == n2 or k == n3:
				return 0
			if A[i] == B[j] and B[j] == C[k]:
				if dp[i + 1][j + 1][k + 1] == -1:
					dp[i + 1][j + 1][k + 1] = helper(A, B, C, i + 1, j + 1, k + 1, n1, n2, n3, dp)
					return 1 + dp[i + 1][j + 1][k + 1]
				else:
					return 1 + dp[i + 1][j + 1][k + 1]
			else:
				if dp[i][j][k + 1] == -1:
					dp[i][j][k + 1] = helper(A, B, C, i, j, k + 1, n1, n2, n3, dp)
					ans1 = dp[i][j][k + 1]
				else:
					ans1 = dp[i][j][k + 1]
				if dp[i][j + 1][k] == -1:
					dp[i][j + 1][k] = helper(A, B, C, i, j + 1, k, n1, n2, n3, dp)
					ans2 = dp[i][j + 1][k]
				else:
					ans2 = dp[i][j + 1][k]
				if dp[i + 1][j][k] == -1:
					dp[i + 1][j][k] = helper(A, B, C, i + 1, j, k, n1, n2, n3, dp)
					ans3 = dp[i + 1][j][k]
				else:
					ans3 = dp[i + 1][j][k]
				return max(ans1, ans2, ans3)
		return helper(A, B, C, 0, 0, 0, n1, n2, n3, dp)


class Solution:

	def LCSof3(self, A, B, C, n1, n2, n3):
		dp = [[[-1 for i in range(n3 + 1)] for j in range(n2 + 1)] for k in range(n1 + 1)]

		def dfs(n1, n2, n3):
			if n1 == 0 or n2 == 0 or n3 == 0:
				return 0
			if dp[n1][n2][n3] != -1:
				return dp[n1][n2][n3]
			if A[n1 - 1] == B[n2 - 1] == C[n3 - 1]:
				dp[n1][n2][n3] = 1 + dfs(n1 - 1, n2 - 1, n3 - 1)
			else:
				dp[n1][n2][n3] = max(dfs(n1 - 1, n2, n3), dfs(n1, n2 - 1, n3), dfs(n1, n2, n3 - 1))
			return dp[n1][n2][n3]
		return dfs(n1, n2, n3)


class Solution:

	def LCSof3(self, A, B, C, n1, n2, n3):

		def dpfun(n, m, p):
			if n < 0 or m < 0 or p < 0:
				return 0
			if dp[n][m][p] != -1:
				return dp[n][m][p]
			if A[n] == B[m] and A[n] == C[p]:
				dp[n][m][p] = 1 + dpfun(n - 1, m - 1, p - 1)
			else:
				dp[n][m][p] = max(dpfun(n - 1, m, p), dpfun(n, m - 1, p), dpfun(n, m, p - 1))
			return dp[n][m][p]
		dp = [[[-1 for _ in range(n3)] for _ in range(n2)] for _ in range(n1)]
		return dpfun(n1 - 1, n2 - 1, n3 - 1)


class Solution:

	def LCSof3(self, a, b, c, n1, n2, n3):
		dp = [[[0] * (n3 + 1) for j in range(n2 + 1)] for i in range(n1 + 1)]
		for i in range(n1 - 1, -1, -1):
			for j in range(n2 - 1, -1, -1):
				for k in range(n3 - 1, -1, -1):
					dp[i][j][k] = max(dp[i + 1][j][k], dp[i][j + 1][k], dp[i][j][k + 1], dp[i + 1][j + 1][k + 1] + int(a[i] == b[j] == c[k]))
		return dp[0][0][0]


class Solution:

	def LCSof3(self, A, B, C, n1, n2, n3):
		t = [[[-1 for i in range(30)] for j in range(30)] for k in range(30)]
		ans = self.LCS(A, B, C, n1, n2, n3, t)
		return ans

	def LCS(self, A, B, C, n1, n2, n3, t):
		if n1 == 0 or n2 == 0 or n3 == 0:
			return 0
		if t[n1][n2][n3] != -1:
			return t[n1][n2][n3]
		if A[n1 - 1] == B[n2 - 1] and B[n2 - 1] == C[n3 - 1]:
			t[n1][n2][n3] = 1 + self.LCS(A, B, C, n1 - 1, n2 - 1, n3 - 1, t)
		else:
			t[n1][n2][n3] = max(max(self.LCS(A, B, C, n1 - 1, n2, n3, t), self.LCS(A, B, C, n1, n2 - 1, n3, t)), self.LCS(A, B, C, n1, n2, n3 - 1, t))
		return t[n1][n2][n3]


from itertools import combinations

class Solution:

	def LCSof3(self, A, B, C, n1, n2, n3):
		x = [[[0 for i in range(n3 + 1)] for j in range(n2 + 1)] for k in range(n1 + 1)]
		for i in range(n1 - 1, -1, -1):
			for j in range(n2 - 1, -1, -1):
				for k in range(n3 - 1, -1, -1):
					if A[i] == B[j] == C[k]:
						x[i][j][k] = 1 + x[i + 1][j + 1][k + 1]
					else:
						x[i][j][k] = max(x[i + 1][j][k], x[i][j + 1][k], x[i][j][k + 1])
		return x[0][0][0]


class Solution:

	def LCSof3(self, A, B, C, n1, n2, n3):
		m = len(A)
		n = len(B)
		p = len(C)
		dp = [[[0 for _ in range(p + 1)] for _ in range(n + 1)] for _ in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				for k in range(1, p + 1):
					if A[i - 1] == B[j - 1] and B[j - 1] == C[k - 1]:
						dp[i][j][k] = 1 + dp[i - 1][j - 1][k - 1]
					else:
						dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j - 1][k], dp[i][j][k - 1])
		return dp[m][n][p]


class Solution:

	def LCSof3(self, A, B, C, n1, n2, n3):
		import functools

		@functools.lru_cache(None)
		def dfs(i, j, k):
			if i == n1 or j == n2 or k == n3:
				return 0
			answer = 0
			if A[i] == B[j] and B[j] == C[k]:
				answer = max(answer, 1 + dfs(i + 1, j + 1, k + 1))
			else:
				answer = max(answer, dfs(i, j, k + 1), dfs(i, j + 1, k), dfs(i + 1, j, k))
			return answer
		return dfs(0, 0, 0)