Question

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

Answer 1

import Foundation

/*
    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].
*/

func lcs(_ s1: String, _ s2: String) -> (length: Int, sequence: String) {
    let a = Array(s1)   // Convert to array for fast indexing
    let b = Array(s2)

    let n = a.count
    let m = b.count

    // Create DP table initialized with zeros
    var dp = Array(repeating: Array(repeating: 0, count: m + 1), count: n + 1)

    // Fill DP table
    for i in 1...n {
        for j in 1...m {
            if a[i - 1] == b[j - 1] {
                dp[i][j] = dp[i - 1][j - 1] + 1
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
            }
        }
    }

    // Reconstruct the LCS sequence
    let length = dp[n][m]
    var lcsChars = Array(repeating: Character(" "), count: length)

    var i = n
    var j = m
    var index = length - 1

    while i > 0 && j > 0 {
        if a[i - 1] == b[j - 1] {
            // Character is part of LCS
            lcsChars[index] = a[i - 1]
            index -= 1
            i -= 1
            j -= 1
        } else if dp[i - 1][j] > dp[i][j - 1] {
            i -= 1 // Move up
        } else {
            j -= 1 // Move left
        }
    }

    return (length, String(lcsChars))
}

// Usage
let s1 = "AGGTAB"
let s2 = "GXTXAYB"

let result = lcs(s1, s2)

print("String 1: \(s1)")
print("String 2: \(s2)")
print("Length of LCS: \(result.length)")
print("LCS sequence: \(result.sequence)")



/*
run:

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

*/

 

70+ SQL courses for beginners and professionals