





"""simple docstring"""





def 					lowerCAmelCase_      (   SCREAMING_SNAKE_CASE							:				str     ,    SCREAMING_SNAKE_CASE							:				str ):


							'''simple docstring'''







							assert x is not None
							assert y is not None

							__lowerCamelCase   :   Dict       =len(SCREAMING_SNAKE_CASE )
							__lowerCamelCase   :   Optional[int]       =len(SCREAMING_SNAKE_CASE )

							# declaring the array for storing the dp values
							__lowerCamelCase   :   Union[str, Any]       =[[0] * (n + 1) for _ in range(m + 1 )]  # noqa: E741

							for i in range(1     ,    m + 1 ):
														for j in range(1     ,    n + 1 ):
																					__lowerCamelCase   :   int       =1 if x[i - 1] == y[j - 1] else 0

																					__lowerCamelCase   :   Optional[int]       =max(l[i - 1][j]     ,    l[i][j - 1]     ,    l[i - 1][j - 1] + match )

							__lowerCamelCase   :   Any       =''''''
							__lowerCamelCase     ,    __lowerCamelCase   :   Dict       =m, n
							while i > 0 and j > 0:
														__lowerCamelCase   :   Any       =1 if x[i - 1] == y[j - 1] else 0

														if l[i][j] == l[i - 1][j - 1] + match:
																					if match == 1:
																												__lowerCamelCase   :   Any       =x[i - 1] + seq
																					i -= 1
																					j -= 1
														elif l[i][j] == l[i - 1][j]:
																					i -= 1
														else:
																					j -= 1

							return l[m][n], seq


if __name__ == "__main__":
							_UpperCamelCase					      =   'AGGTAB'
							_UpperCamelCase					      =   'GXTXAYB'
							_UpperCamelCase					      =   4
							_UpperCamelCase					      =   'GTAB'

							_UpperCamelCase      ,     _UpperCamelCase					      =   longest_common_subsequence(a, b)
							print('len =', ln, ', sub-sequence =', subseq)
							import doctest

							doctest.testmod()











"""simple docstring"""





from __future__ import annotations



def 					lowerCAmelCase_      (   SCREAMING_SNAKE_CASE							:				list[int | str] ):


							'''simple docstring'''







							create_state_space_tree(SCREAMING_SNAKE_CASE     ,    []     ,    0     ,    [0 for i in range(len(SCREAMING_SNAKE_CASE ) )] )



def 					lowerCAmelCase_      (   SCREAMING_SNAKE_CASE							:				list[int | str]     ,    SCREAMING_SNAKE_CASE							:				list[int | str]     ,    SCREAMING_SNAKE_CASE							:				int     ,    SCREAMING_SNAKE_CASE							:				list[int]     ,    ):


							'''simple docstring'''







							if index == len(SCREAMING_SNAKE_CASE ):
														print(SCREAMING_SNAKE_CASE )
														return

							for i in range(len(SCREAMING_SNAKE_CASE ) ):
														if not index_used[i]:
																					current_sequence.append(sequence[i] )
																					__lowerCamelCase   :   List[Any]       =True
																					create_state_space_tree(SCREAMING_SNAKE_CASE     ,    SCREAMING_SNAKE_CASE     ,    index + 1     ,    SCREAMING_SNAKE_CASE )
																					current_sequence.pop()
																					__lowerCamelCase   :   List[Any]       =False
_UpperCamelCase					      =   [3, 1, 2, 4]
generate_all_permutations(sequence)

_UpperCamelCase					      =   ["A", "B", "C"]
generate_all_permutations(sequence_a)




