Question

How to find the length of the longest common subsequence (LCS) in two strings with Ruby

Answer 1

#
# This program computes BOTH:
#   1. The length of the Longest Common Subsequence (LCS)
#   2. The actual LCS subsequence
#
# It uses an efficient dynamic‑programming algorithm:
#       Time:  O(n * m)
#       Space: O(n * m)
#
# dp[i][j] stores the LCS length between:
#     s1[0..i-1] and s2[0..j-1]
#
# Recurrence:
#   If characters match:
#       dp[i][j] = dp[i-1][j-1] + 1
#   Else:
#       dp[i][j] = max(dp[i-1][j], dp[i][j-1])
#
# After filling the DP table, we reconstruct the LCS by
# walking backwards from dp[n][m].
#

def lcs(s1, s2)
  n = s1.length
  m = s2.length

  # Create DP table initialized with zeros
  dp = Array.new(n + 1) { Array.new(m + 1, 0) }

  # Fill DP table
  (1..n).each do |i|
    (1..m).each do |j|
      if s1[i - 1] == s2[j - 1]
        dp[i][j] = dp[i - 1][j - 1] + 1
      else
        dp[i][j] = [dp[i - 1][j], dp[i][j - 1]].max
      end
    end
  end

  # Reconstruct the LCS sequence
  length = dp[n][m]
  lcs_chars = Array.new(length)

  i = n
  j = m
  index = length - 1

  while i > 0 && j > 0
    if s1[i - 1] == s2[j - 1]
      # Character is part of LCS
      lcs_chars[index] = s1[i - 1]
      index -= 1
      i -= 1
      j -= 1
    elsif dp[i - 1][j] > dp[i][j - 1]
      i -= 1 # Move up
    else
      j -= 1 # Move left
    end
  end

  return length, lcs_chars.join
end

# Usage
s1 = "AGGTAB"
s2 = "GXTXAYB"

length, sequence = lcs(s1, s2)

puts "String 1: #{s1}"
puts "String 2: #{s2}"
puts "Length of LCS: #{length}"
puts "LCS sequence: #{sequence}"


#
# run:
#
# String 1: AGGTAB
# String 2: GXTXAYB
# Length of LCS: 4
# LCS sequence: GTAB
#

 

70+ SQL courses for beginners and professionals