Table of contents
NOTE ON THIS SECTION
These problems are CHALLENGING AND ADVANCED compared to the earlier ones. DO NOT feel discouraged if they are difficult. This section is for those who enjoy pain and misery. You DO NOT need to attempt these problems unless you want to!
Longest repeated subsequence length problem
Create a function to find the length of Longest Repeated Subsequence. The longest repeated subsequence (LRS) is the longest subsequence of a string that occurs at least twice.
Example
LRSLength('ATAKTKGGA',9,9) # 4 LRS = ATKG
Note: 9 is the length of the string.
# Function to find the length of Longest repeated Subsequence
# of substring X[0..m-1] and X[0..n-1]
def LRSLength(X, m, n):
# return if we have reached the end of either string
if m == 0 or n == 0:
return 0
# if characters at index m and n matches and index is different
if X[m - 1] == X[n - 1] and m != n:
return LRSLength(X, m - 1, n - 1) + 1
# else if characters at index m and n don't match
return max(LRSLength(X, m, n - 1), LRSLength(X, m - 1, n))
Longest common subsequence length problem
S1 and S2 are given strings, create a function to find the length of the longest subsequence which is common to both strings.
Subsequence: a sequence that can be driven from another sequence by deleting some elements without changing the order of them
Example
S1 = "ABCBDAB"bS2 = "BDCABA" LCSLength(S1, S2, len(S1), len(S2)) #4
def LCSLength(S1, S2, lenS1, lenS2):
# return if we have reached the end of either sequence
if lenS1 == 0 or lenS2 == 0:
return 0
# if last character of S1 and S2 matches
if S1[lenS1 - 1] == S2[lenS2 - 1]:
return LCSLength(S1, S2, lenS1 - 1, lenS2 - 1) + 1
# else if last character of S1 and S2 don't match
return max(LCSLength(S1, S2, lenS1, lenS2 - 1), LCSLength(S1, S2, lenS1 - 1, lenS2))
Longest common subsequence problem
S1 and S2 are given strings, create a function to print all possible longest subsequence which is common to both strings.
Subsequence: a sequence that can be driven from another sequence by deleting some elements without changing the order of them
Example
Input: S1 = "ABCBDAB"S2 = "BDCABA" Ouput: "BCAB""BCBA""BDAB"
# Function to find LCS of X[0..m-1] and Y[0..n-1]
def LCS(X, Y, m, n, T):
#TO-DO
# return empty string if we have reached the end of
# either sequence
if m == 0 or n == 0:
return str()
# if last character of X and Y matches
if X[m - 1] == Y[n - 1]:
# append current character (X[m-1] or Y[n-1]) to LCS of
# substring X[0..m-2] and Y[0..n-2]
return LCS(X, Y, m - 1, n - 1, T) + X[m - 1]
# else when the last character of X and Y are different
# if top cell of current cell has more value than the left
# cell, then drop current character of X and find LCS
# of substring X[0..m-2], Y[0..n-1]
if T[m - 1][n] > T[m][n - 1]:
return LCS(X, Y, m - 1, n, T)
else:
# if left cell of current cell has more value than the top
# cell, then drop current character of Y and find LCS
# of substring X[0..m-1], Y[0..n-2]
return LCS(X, Y, m, n - 1, T)
# Function to fill lookup table by finding the length of LCS
# of substring X[0..m-1] and Y[0..n-1]
def LCSLength(X, Y, m, n, T):
# fill the lookup table in bottom-up manner
for i in range(1, m + 1):
for j in range(1, n + 1):
# if current character of X and Y matches
if X[i - 1] == Y[j - 1]:
T[i][j] = T[i - 1][j - 1] + 1
# else if current character of X and Y don't match
else:
T[i][j] = max(T[i - 1][j], T[i][j - 1])
X = "ABCBDAB"
Y = "BDCABA"
m = len(X)
n = len(Y)
# T[i][j] stores the length of LCS of substring X[0..i-1], Y[0..j-1]
T = [[0 for x in range(n + 1)] for y in range(m + 1)]
# fill lookup table
LCSLength(X, Y, m, n, T)
# find longest common sequence
print(LCS(X, Y, m, n, T))
Diff utility
Given two similar strings, implement your own diff utility to list out all differences between them.
Diff Utility : It is a data comparison tool that calculates and displays the differences between two text.
Example
Input:
S1 = 'XMJYAUZ'S2 = 'XMJAATZ'
Output:
XMJ-YA-U+A+TZ
- indicates that character is deleted from S2 but it was present in S1
+ indicates that character is inserted in S2 but it was not present in S1
Hint:
You can use Longest Common Subsequence (LCS) to solve this problem. The idea is to find a longest sequence of characters that is present in both original sequences in the same order. From a longest common subsequence it is only a small step to get diff-like output:
if a character is absent in the subsequence but present in the first original sequence, it must have been deleted (indicated by the '-' marks)
if it is absent in the subsequence but present in the second original sequence, it must have been inserted (indicated by the '+' marks)
# Function to display the differences between two Strings
def diff(S1, S2, m, n, lookup):
# if last character of S1 and S2 matches
if m > 0 and n > 0 and S1[m - 1] == S2[n - 1]:
diff(S1, S2, m - 1, n - 1, lookup)
print("", S1[m - 1], end='')
# current character of S2 is present not in S1
elif n > 0 and (m == 0 or lookup[m][n - 1] >= lookup[m - 1][n]):
diff(S1, S2, m, n - 1, lookup)
print(" +" + S2[n - 1], end='')
# current character of S1 is present not in S2
elif m > 0 and (n == 0 or lookup[m][n - 1] < lookup[m - 1][n]):
diff(S1, S2, m - 1, n, lookup)
print(" -" + S1[m - 1], end='')
# Function to fill lookup table by finding the length of LCS
# of subS1[0..m-1] and S2[0..n-1]
def LCSLength(S1, S2, m, n, lookup):
# first column of the lookup table will be all 0
for i in range(m + 1):
lookup[i][0] = 0
# first row of the lookup table will be all 0
for j in range(n + 1):
lookup[0][j] = 0
# fill the lookup table in bottom-up manner
for i in range(1, m + 1):
for j in range(1, n + 1):
# if current character of S1 and S2 matches
if S1[i - 1] == S2[j - 1]:
lookup[i][j] = lookup[i - 1][j - 1] + 1
# else if current character of S1 and S2 don't match
else:
lookup[i][j] = max(lookup[i - 1][j], lookup[i][j - 1])
S1 = "ABCDFGHJQZ"
S2 = "ABCDEFGIJKRXYZ"
# lookup[i][j] stores the length of LCS of subS1[0..i-1], S2[0..j-1]
lookup = [[0 for x in range(len(S2) + 1)] for y in range(len(S1) + 1)]
# fill lookup table
LCSLength(S1, S2, len(S1), len(S2), lookup)
# find difference
diff(S1, S2, len(S1), len(S2), lookup)
Shortest common super sequence problem
The shortest common super sequence (SCS) is the problem of finding the shortest super sequence supSeq of given sequences S1 and S2 such that both these sequences are subseqeunce of supSeq.
Example
S1 = "ABCBDAB"S2 = "BDCABA" SCSLength(S1, S2, len(S1), len(S2)) #9
def SCSLength(X, Y, m, n):
# if we have reached the end of either sequence, return
# length of other sequence
if m == 0 or n == 0:
return n + m
# if last character of X and Y matches
if X[m - 1] == Y[n - 1]:
return SCSLength(X, Y, m - 1, n - 1) + 1
# last character of X and Y don't match
return min(SCSLength(X, Y, m, n - 1) + 1, SCSLength(X, Y, m - 1, n) + 1)
Length of longest palindromic subsequence
Given a sequence, find the length of the longest palindromic subsequence in it using dynamic programming.
Palindrome is a string that reads the same backward as well as forward.
Example:
lps("ABABCBA") # 5
def lps(str):
n = len(str)
L = [[0 for x in range(n)] for x in range(n)]
for i in range(n):
L[i][i] = 1
for cl in range(2, n+1):
for i in range(n-cl+1):
j = i+cl-1
if str[i] == str[j] and cl == 2:
L[i][j] = 2
elif str[i] == str[j]:
L[i][j] = L[i+1][j-1] + 2
else:
L[i][j] = max(L[i][j-1], L[i+1][j]);
return L[0][n-1]
Subset sum problem
Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.
Example:
Input: [3, 34, 4, 12, 5, 2], sum = 9Output: True There is a subset (4, 5) with sum 9. Input: [3, 34, 4, 12, 5, 2], sum = 30Output: FalseThere is no subset that add up to 30.
def isSubsetSum(set, n, sum):
# The value of subset[i][j] will be
# true if there is a
# subset of set[0..j-1] with sum equal to i
subset =([[False for i in range(sum + 1)]
for i in range(n + 1)])
# If sum is 0, then answer is true
for i in range(n + 1):
subset[i][0] = True
for i in range(1, sum + 1):
subset[0][i]= False
for i in range(1, n + 1):
for j in range(1, sum + 1):
if j<set[i-1]:
subset[i][j] = subset[i-1][j]
if j>= set[i-1]:
subset[i][j] = (subset[i-1][j] or
subset[i - 1][j-set[i-1]])
return subset[n][sum]
Egg dropping puzzle
The following is a description of the instance of this famous puzzle involving N=2 eggs and a building with H=36 floors:
Suppose that we wish to know which stories in a 36-story building are safe to drop eggs from, and which will cause the eggs to break on landing. We make a few assumptions:
An egg that survives a fall can be used again.
A broken egg must be discarded.
The effect of a fall is the same for all eggs.
If an egg breaks when dropped, then it would break if dropped from a higher window.
If an egg survives a fall, then it would survive a shorter fall.
It is not ruled out that the first-floor windows break eggs, nor is it ruled out that eggs can survive the 36th-floor windows.
If only one egg is available and we wish to be sure of obtaining the right result, the experiment can be carried out in only one way. Drop the egg from the first-floor window; if it survives, drop it from the second-floor window. Continue upward until it breaks. In the worst case, this method may require 36 droppings. Suppose 2 eggs are available. What is the lowest number of egg-droppings that is guaranteed to work in all cases?
INT_MAX = 32767
# Function to get minimum number of trials needed in worst
# case with n eggs and k floors
def eggDrop(n, k):
# to-do
# A 2D table where entery eggFloor[i][j] will represent minimum
# number of trials needed for i eggs and j floors.
eggFloor = [[0 for x in range(k + 1)] for x in range(n + 1)]
# We need one trial for one floor and0 trials for 0 floors
for i in range(1, n + 1):
eggFloor[i][1] = 1
eggFloor[i][0] = 0
# We always need j trials for one egg and j floors.
for j in range(1, k + 1):
eggFloor[1][j] = j
# Fill rest of the entries in table using optimal substructure
# property
for i in range(2, n + 1):
for j in range(2, k + 1):
eggFloor[i][j] = INT_MAX
for x in range(1, j + 1):
res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x])
if res < eggFloor[i][j]:
eggFloor[i][j] = res
# eggFloor[n][k] holds the result
return eggFloor[n][k]
Maximum length chain of pairs
You are given n pairs of numbers. In every pair, the first number is always smaller than the second number. A pair (c, d) can follow another pair (a, b) if b < c. Chain of pairs can be formed in this fashion. Find the longest chain which can be formed from a given set of pairs.
Example
If the given pairs are {{5, 24}, {39, 60}, {15, 28}, {27, 40}, {50, 90} }, then the longest chain that can be formed is of length 3, and the chain is {{5, 24}, {27, 40}, {50, 90}}
class Pair(object):
def __init__(self, a, b):
self.a = a
self.b = b
def maxChainLength(arr, n):
max = 0
mcl = [1 for i in range(n)]
for i in range(1, n):
for j in range(0, i):
if (arr[i].a > arr[j].b and
mcl[i] < mcl[j] + 1):
mcl[i] = mcl[j] + 1
for i in range(n):
if (max < mcl[i]):
max = mcl[i]
return max