Leetcode Prep Basics

Q1: Find the longest substring (LS) without repetition.

Ans:

def find_ls(text):
    n = len(text)
    max_len = 0  # To store the maximum length of a substring with unique characters

    for i in range(n):  # Iterate through each starting point
        seen = set()  # To track characters in the current substring
        for j in range(i, n):  # Iterate through the rest of the string
            if text[j] not in seen:  # If the character is unique
                seen.add(text[j])
                max_len = max(max_len, len(seen))  # Update max length if needed
            else:
                break  # Stop if a duplicate character is found

    return max_len

Approach 2: To return the longest length of the substring along with the substring itself.

def find_ls(text):
    n = len(text)
    max_len = 0  # To store the maximum length of a unique substring
    longest_substring = ""  # To store the longest unique substring

    for i in range(n):
        seen = set()  # To track characters in the current substring
        current_substring = ""  # To store the current substring
        for j in range(i, n):
            if text[j] not in seen:
                seen.add(text[j])
                current_substring += text[j]
                if len(current_substring) > max_len:
                    max_len = len(current_substring)
                    longest_substring = current_substring
            else:
                break  # Stop if a duplicate character is found

    return max_len, longest_substring

**Q 2: Target Sum: You are given an integer array nums and an integer target. You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers. For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1". Return the number of different expressions that you can build, which evaluates to target.

Question link: https://leetcode.com/problems/target-sum/description/ Answer:

def findTargetSumWays(nums, target):
    n = len(nums)
    summation = sum(nums)
    dp = [[None]*(2*summation+1) for _ in range(n)]

    def helper(index,sum_nums):
        #base case
        if index<0:
            if sum_nums==target:return 1
            else:return 0
        if dp[index][sum_nums+summation]!=None:return dp[index][sum_nums+summation]

        negative = helper(index-1,sum_nums+-1*nums[index])
        positive = helper(index-1,sum_nums+nums[index])    
        dp[index][sum_nums+summation] = negative+positive
        return dp[index][sum_nums+summation]
    return helper(n-1,0) 

**Q 3: Partition Equal Subset Sum: Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Question link: https://leetcode.com/problems/partition-equal-subset-sum/description/ Answer:

def canPartition(nums):
    n = len(nums)
    sum = 0
    for num in nums:
        sum+=num
    if sum%2 !=0: return False
    target =sum//2
    prev = [False]*(target+1) 
    curr = [False]*(target+1)
    prev[0]=True
    curr[0]=True

    for i in range(1,n+1):
        for j in range(1, target+1):
            #pick
            if nums[i-1]<=j:
                curr[j] = prev[j-nums[i-1]]
            else:
                curr[j] = False    
            #dontpick
            curr[j] = curr[j] or prev[j]
            
        prev = curr[:]  
    return curr[target]  

Q3: Longest increasing subsequence Question Link: https://leetcode.com/problems/longest-increasing-subsequence/description/

Answer:

def lengthOfLIS(nums):
    n = len(nums)
    dp = [[0]*(n+1) for _ in range(n+1)]

    for i in range(n-1,-1,-1):
        for j in range(i,-1,-1):
            exclude = dp[i+1][j]
            include = 0
            if j-1 ==-1 or nums[i]>nums[j-1]:
                include = 1 + dp[i+1][i+1]
            dp[i][j] = max(exclude,include)
    return dp[0][0]