<jupyter_start><jupyter_text>Dynamic Programming - Sequence Problems  Maximum Length of Repeated SubarrayGiven two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.Source: https://leetcode.com/problems/maximum-length-of-repeated-subarray/Example 1:```Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]Output: 3Explanation: The repeated subarray with maximum length is [3,2,1].```Example 2:```Input: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]Output: 5```<jupyter_code>class Solution:
    def findLength(self, nums1, nums2):
        '''
        '''
        
        L1 = len(nums1)
        L2 = len(nums2)
        
        count_repeat = []
        temp_max = 0
        
        for i in range(L1+1):
            count_repeat.append([])
            for j in range(L2+1):
                count_repeat[i].append(0)
                
        for i in range(1, L1+1):
            for j in range(1, L2+1):
                if nums1[i-1] == nums2[j-1]:
                    count_repeat[i][j] = count_repeat[i-1][j-1] + 1
                    temp_max = max(temp_max, count_repeat[i][j])
        return temp_max
                
solver = Solution()
solver.findLength([0,0,0,0,0], [0,0,0,0,0,0])
solver = Solution()
solver.findLength([1,2,3,2,1], [3,2,1,4,7])<jupyter_output><empty_output><jupyter_text>Uncrossed LinesYou are given two integer arrays nums1 and nums2. We write the integers of nums1 and nums2 (in the order they are given) on two separate horizontal lines.We may draw connecting lines: a straight line connecting two numbers nums1[i] and nums2[j] such that:* `nums1[i] == nums2[j]`, and* the line we draw does not intersect any other connecting (non-horizontal) line.Note that a connecting line cannot intersect even at the endpoints (i.e., each number can only belong to one connecting line).Return the maximum number of connecting lines we can draw in this way.Source: https://leetcode.com/problems/uncrossed-lines/Example 1:```Input: nums1 = [1,4,2], nums2 = [1,2,4]Output: 2Explanation: We can draw 2 uncrossed lines as in the diagram.We cannot draw 3 uncrossed lines, because the line from nums1[1] = 4 to nums2[2] = 4 will intersect the line from nums1[2]=2 to nums2[1]=2.```Example 2:```Input: nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]Output: 3```Example 3:```Input: nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]Output: 2```<jupyter_code>class Solution:
    def maxUncrossedLines(self, nums1, nums2):
        '''
        '''
        
        L1 = len(nums1)
        L2 = len(nums2)
        
        count_line = []
        
        for i in range(L1+1):
            count_line.append([])
            
            for j in range(L2+1):
                count_line[i].append(0)
                
        for i in range(1, L1+1):
            for j in range(1, L2+1):
                if nums1[i-1] == nums2[j-1]:
                    count_line[i][j] = count_line[i-1][j-1]+1
                else:
                    count_line[i][j] = max(count_line[i-1][j], count_line[i][j-1])
                    
                
        return count_line[-1][-1]
                
solver = Solution()
solver.maxUncrossedLines([1,4,2], [1,2,4])<jupyter_output><empty_output><jupyter_text>Longest Common SubsequenceGiven two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.For example, "ace" is a subsequence of "abcde".A common subsequence of two strings is a subsequence that is common to both strings.Source: https://leetcode.com/problems/longest-common-subsequence/Example 1:```Input: text1 = "abcde", text2 = "ace" Output: 3  Explanation: The longest common subsequence is "ace" and its length is 3.```Example 2:```Input: text1 = "abc", text2 = "abc"Output: 3Explanation: The longest common subsequence is "abc" and its length is 3.```Example 3:```Input: text1 = "abc", text2 = "def"Output: 0Explanation: There is no such common subsequence, so the result is 0.```<jupyter_code>class Solution:
    def longestCommonSubsequence(self, text1, text2):
        '''
        '''
        
        L1 = len(text1)
        L2 = len(text2)
        
        count_seq = []
        
        for i in range(L1+1):
            count_seq.append([])
            for j in range(L2+1):
                count_seq[i].append(0)
                
        for i in range(1, L1+1):
            for j in range(1, L2+1):
                if text1[i-1] == text2[j-1]:
                    count_seq[i][j] = count_seq[i-1][j-1] + 1
                else:
                    count_seq[i][j] = max(count_seq[i][j-1], count_seq[i-1][j])
                    
        return count_seq
                
solver = Solution()
solver.longestCommonSubsequence("abcde", "ace")<jupyter_output><empty_output><jupyter_text>Longest Continuous Increasing SubsequenceGiven an unsorted array of integers nums, return the length of the longest continuous increasing subsequence (i.e. subarray). The subsequence must be strictly increasing.A continuous increasing subsequence is defined by two indices l and r (l < r) such that it is [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] and for each l <= i < r, nums[i] < nums[i + 1].Source: https://leetcode.com/problems/longest-continuous-increasing-subsequence/Example 1:```Input: nums = [1,3,5,4,7]Output: 3Explanation: The longest continuous increasing subsequence is [1,3,5] with length 3.Even though [1,3,5,7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element4.```Example 2:```Input: nums = [2,2,2,2,2]Output: 1Explanation: The longest continuous increasing subsequence is [2] with length 1. Note that it must be strictlyincreasing.```<jupyter_code>class Solution:
    def findLengthOfLCIS(self, nums):
        '''
        '''
        
        L = len(nums)
        
        count_length = [1,]*(L)
        temp_max = 1
        for i in range(1, L):
            if nums[i] > nums[i-1]:
                count_length[i] = count_length[i-1]+1
                temp_max = max(count_length[i], temp_max)
            # !!! <--- no else
            #else:
                #count_length[i] = count_length[i+1]
        return temp_max
        
        
solver = Solution()
solver.findLengthOfLCIS([1,3,5,4,7])<jupyter_output><empty_output><jupyter_text>**Longest Increasing Subsequence**Given an integer array nums, return the length of the longest strictly increasing subsequence.A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].Source: https://leetcode-cn.com/problems/longest-increasing-subsequence/Example 1:```Input: nums = [10,9,2,5,3,7,101,18]Output: 4Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.```Example 2:```Input: nums = [0,1,0,3,2,3]Output: 4```Example 3:```Input: nums = [7,7,7,7,7,7,7]Output: 1```<jupyter_code>class Solution:
    def lengthOfLIS(self, nums):
        '''
        '''
        
        L = len(nums)
        
        count_ascend = [1,]*(L)
        temp_max = 0
        
        for i in range(1, L):
            if nums[i] > nums[i-1]:
                count_ascend[i] = count_ascend[i-1] + 1
                temp_max = max(temp_max, count_ascend[i])
            else:
                count_ascend[i] = count_ascend[i-1]
            
        return temp_max
solver = Solution()
solver.lengthOfLIS([10,9,2,5,3,7,101,18])<jupyter_output><empty_output><jupyter_text>Shortest Common SupersequenceGiven two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If there are multiple valid strings, return any of them.A string s is a subsequence of string t if deleting some number of characters from t (possibly 0) results in the string s.Source: https://leetcode.com/problems/shortest-common-supersequence/Example 1:```Input: str1 = "abac", str2 = "cab"Output: "cabac"Explanation: str1 = "abac" is a subsequence of "cabac" because we can delete the first "c".str2 = "cab" is a subsequence of "cabac" because we can delete the last "ac".The answer provided is the shortest such string that satisfies these properties.```Example 2:```Input: str1 = "aaaaaaaa", str2 = "aaaaaaaa"Output: "aaaaaaaa"```<jupyter_code>class Solution:
    def shortestCommonSupersequence(self, str1, str2):
        '''
        '''
        
        L1 = len(str1)
        L2 = len(str2)
        
        SCS = []
        for i in range(L1+1):
            SCS.append([])
            for j in range(L2+1):
                SCS[i].append('')
        
        for i in range(1, L1+1):
            SCS[i][0] = str1[:i]
            
        for j in range(1, L2+1):
            SCS[0][j] = str2[:j]
                
        for i in range(1, L1+1):
            for j in range(1, L2+1):
                
                if str1[i-1] == str2[j-1]:
                    SCS[i][j] = SCS[i-1][j-1] + str1[i-1]
                else:
                    temp_L1 = len(SCS[i-1][j])
                    temp_L2 = len(SCS[i][j-1])
                    if temp_L1 > temp_L2:
                        SCS[i][j] = SCS[i][j-1] + str1[i-1]
                    else:
                        SCS[i][j] = SCS[i-1][j] + str1[i-1]
                        
        return SCS[-1][-1]
                
            
        
        
solver = Solution()
solver.shortestCommonSupersequence("abac", "cab")<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12723145186255289, 'fraction_numerical': 0.040346713445464866, 'mean_word_length': 2.4466571834992887, 'pattern_counts': {'":': 0, '<': 30, '<?xml version=': 0, '>': 28, 'https://': 6, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 3, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '612377', 'license': 'Unlicense', 'n_tokens_mistral': 3355, 'n_tokens_neox': 3179, 'n_words': 885, 'path': 'Python/Dynamic_Programming_Sequence_Problems.ipynb', 'repo_name': 'yingkaisha/notebook_code_vault', 'size': '9691'}