DYNAMIC PROGRAMMING | LONGEST COMMON SUB SEQUENCE | LONGEST REPEATING SUB SEQUENCE | REPEATED SUB SEQUENCE OF LENGTH 2 OR MORE

By: Saurav

2018-04-07 05:20:00 UTC

These three tough looking problems are based on the same concept. let's solve the first one and identify the subproblem and guess the solution for the base case.

Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. So a string of length n has 2^n different possible subsequences.

LONGEST COMMON SUB SEQUENCE

A simple strategy is to go and find out each substring of the two inputs. As we know that will be exponential complexity as the total number of solutions will be 2**n.

A simpler problem can be to take the last characters of the two strings.
If they are equal, add 1 to whatever is the result of the subproblems consisting of a substring in the two strings without the last one. That means longest common subsequence at last index would be 1 + the result we get from the remaining substrings. If they are not equal, it will be the maximum of alternate substrings.

A graph structure like below explains the recursive tree

                         lcs("AXYT", "AYZX")
                       /                 
         lcs("AXY", "AYZX")            lcs("AXYT", "AYZ")
         /                              /               
lcs("AX", "AYZX") lcs("AXY", "AYZ")   lcs("AXY", "AYZ") lcs("AXYT", "AY")

We see that lcs(“AXY”, “AYZ”) is being solved two times. Now that we understand that there is a substructure involved, lets use dynamic programming to solve this optimally:

def longest_common_subsequence(a,b)
  m = a.size 
  n = b.size 
  a = a.downcase
  b = b.downcase
  
  arr = Array.new(m+1){Array.new(n+1, 0)}
  
  (1..m).each do |i|
    (1..n).each do |j|
      if a[i-1] == b[j-1]
        arr[i][j] = arr[i-1][j-1] + 1 
      else   
        arr[i][j] = [arr[i-1][j], arr[i][j-1]].max
      end 
    end
  end
  
  return arr[-1][-1]
  
end 

p longest_common_subsequence('ABCDGH', 'AEDFHR')
p longest_common_subsequence('AGGTAB', 'GXTXAYB')
p longest_common_subsequence('abcdaf', 'acbcf')

if you run it, you will see all our tests pass and we expected results.

LONGEST REPEATING SUB SEQUENCE

Now let's move on to the second and third question which is derived from the first one. Now, I want to find the repeated subsequence. Since the first one solves the common subsequence between two strings, the only thing to check if we compare a string with itself is the index of the subsequence should not be the same and yet the elements are the same and then we will get a new subsequence which is repeated in the string itself.

Lets modify the algorithm to handle the new requirement:

def longest_repeating_subsequence(a)
  m = a.size 
  n = a.size 
  a = a.downcase
  b = a
  
  arr = Array.new(m+1){Array.new(n+1, 0)}
  
  (1..m).each do |i|
    (1..n).each do |j|
      if a[i-1] == b[j-1] and i != j
        arr[i][j] = arr[i-1][j-1] + 1 
      else   
        arr[i][j] = [arr[i-1][j], arr[i][j-1]].max
      end 
    end
  end
  
  return arr[-1][-1]
  
end 

p longest_repeating_subsequence('axxxy')


REPEATED SUB SEQUENCE OF LENGTH 2 OR MORE

The only thing to add to the previous code is a check that our code returns a length more than 2:

   def anytwo(a)
      m = a.size 
      n = a.size 
      a = a
      b = a
      
      arr = Array.new(m+1){Array.new(n+1, 0)}
      
      (1..m).each do |i|
        (1..n).each do |j|
          if a[i-1] == b[j-1] and i != j
            arr[i][j] = arr[i-1][j-1] + 1 
          else   
            arr[i][j] = [arr[i-1][j], arr[i][j-1]].max
          end 
        end
      end
      
      arr[-1][-1] > 1 ? 1 : 0
      
    end 


Let me know what you think!
twitter: sprakash24oct
linkedin

Owned & Maintained by Saurav Prakash

If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :)