Longest Common Subsequence (LCS)

Problem Təsviri

İki sətir verilmişdir. Onların ən uzun ümumi alt-ardıcıllığının uzunluğunu tapın. Alt-ardıcıllıq, əsas sətirdən bəzi elementləri silərək əldə edilir (ardıcıllıq saxlanılır).

Məsələn:

text1 = "abcde", text2 = "ace"
- LCS = "ace", uzunluq = 3
text1 = "abc", text2 = "abc"
- LCS = "abc", uzunluq = 3
text1 = "abc", text2 = "def"
- LCS = "", uzunluq = 0

Qeyd: Subsequence ≠ Substring

Subsequence: ardıcıl olması lazım deyil ("ace" is subsequence of "abcde")
Substring: ardıcıl olmalıdır ("abc" is substring of "abcde")

Recurrence Relation:

if s1[i] == s2[j]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Müxtəlif Yanaşmalar

1. Sadə Rekursiya (Naive Approach)

Koda bax

public class LCSNaive {
    
    public static int longestCommonSubsequence(String text1, String text2) {
        return lcs(text1, text2, text1.length(), text2.length());
    }
    
    private static int lcs(String s1, String s2, int m, int n) {
        // Base cases
        if (m == 0 || n == 0) {
            return 0;
        }
        
        // If last characters match
        if (s1.charAt(m - 1) == s2.charAt(n - 1)) {
            return 1 + lcs(s1, s2, m - 1, n - 1);
        }
        
        // If last characters don't match
        return Math.max(
            lcs(s1, s2, m - 1, n),
            lcs(s1, s2, m, n - 1)
        );
    }
    
    public static void main(String[] args) {
        System.out.println("LCS (Naive Recursion):");
        
        String text1 = "abcde";
        String text2 = "ace";
        System.out.println("text1: " + text1 + ", text2: " + text2);
        System.out.println("LCS length: " + longestCommonSubsequence(text1, text2));
        
        String text3 = "abc";
        String text4 = "abc";
        System.out.println("\ntext1: " + text3 + ", text2: " + text4);
        System.out.println("LCS length: " + longestCommonSubsequence(text3, text4));
        
        String text5 = "abc";
        String text6 = "def";
        System.out.println("\ntext1: " + text5 + ", text2: " + text6);
        System.out.println("LCS length: " + longestCommonSubsequence(text5, text6));
    }
}

Mürəkkəblik:

Time Complexity: O(2^(m+n)) - Eksponensial
Space Complexity: O(m+n) - Rekursiya stack-i

Problemlər:

Çox yavaş uzun sətirlər üçün
Eyni alt-problemlər dəfələrlə hesablanır

2. Memoization (Top-Down DP)

Koda bax

import java.util.HashMap;
import java.util.Map;

public class LCSMemoization {
    
    // Using 2D array for memoization
    public static int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        int[][] memo = new int[m + 1][n + 1];
        
        // Initialize with -1 (not computed)
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                memo[i][j] = -1;
            }
        }
        
        return lcs(text1, text2, m, n, memo);
    }
    
    private static int lcs(String s1, String s2, int m, int n, int[][] memo) {
        // Base cases
        if (m == 0 || n == 0) {
            return 0;
        }
        
        // Check if already computed
        if (memo[m][n] != -1) {
            return memo[m][n];
        }
        
        // If last characters match
        if (s1.charAt(m - 1) == s2.charAt(n - 1)) {
            memo[m][n] = 1 + lcs(s1, s2, m - 1, n - 1, memo);
        } else {
            // If last characters don't match
            memo[m][n] = Math.max(
                lcs(s1, s2, m - 1, n, memo),
                lcs(s1, s2, m, n - 1, memo)
            );
        }
        
        return memo[m][n];
    }
    
    // Alternative: Using HashMap with string key
    private static Map<String, Integer> memoMap = new HashMap<>();
    
    public static int longestCommonSubsequenceMap(String text1, String text2) {
        memoMap.clear();
        return lcsWithMap(text1, text2, text1.length(), text2.length());
    }
    
    private static int lcsWithMap(String s1, String s2, int m, int n) {
        if (m == 0 || n == 0) return 0;
        
        String key = m + "," + n;
        if (memoMap.containsKey(key)) {
            return memoMap.get(key);
        }
        
        int result;
        if (s1.charAt(m - 1) == s2.charAt(n - 1)) {
            result = 1 + lcsWithMap(s1, s2, m - 1, n - 1);
        } else {
            result = Math.max(
                lcsWithMap(s1, s2, m - 1, n),
                lcsWithMap(s1, s2, m, n - 1)
            );
        }
        
        memoMap.put(key, result);
        return result;
    }
    
    public static void main(String[] args) {
        System.out.println("LCS (Memoization):");
        
        String text1 = "abcde";
        String text2 = "ace";
        System.out.println("text1: " + text1 + ", text2: " + text2);
        System.out.println("LCS length: " + longestCommonSubsequence(text1, text2));
        
        String text3 = "aggtab";
        String text4 = "gxtxayb";
        System.out.println("\ntext1: " + text3 + ", text2: " + text4);
        long startTime = System.currentTimeMillis();
        System.out.println("LCS length: " + longestCommonSubsequence(text3, text4));
        long endTime = System.currentTimeMillis();
        System.out.println("Vaxt: " + (endTime - startTime) + " ms");
    }
}

Mürəkkəblik:

Time Complexity: O(m * n)
Space Complexity: O(m * n) - Memo table və rekursiya stack-i

3. Tabulation (Bottom-Up DP)

Koda bax

public class LCSTabulation {
    
    public static int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        
        // Create DP table
        int[][] dp = new int[m + 1][n + 1];
        
        // Base case: dp[0][j] = 0 and dp[i][0] = 0 (already initialized)
        
        // Fill table bottom-up
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        return dp[m][n];
    }
    
    // Method to print DP table
    public static void printDPTable(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        System.out.println("\nDP Table:");
        System.out.print("    ");
        for (char c : text2.toCharArray()) {
            System.out.print(c + " ");
        }
        System.out.println();
        
        for (int i = 0; i <= m; i++) {
            if (i > 0) System.out.print(text1.charAt(i - 1) + " ");
            else System.out.print("  ");
            
            for (int j = 0; j <= n; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
    }
    
    public static void main(String[] args) {
        System.out.println("LCS (Tabulation):");
        
        String text1 = "abcde";
        String text2 = "ace";
        System.out.println("text1: " + text1 + ", text2: " + text2);
        System.out.println("LCS length: " + longestCommonSubsequence(text1, text2));
        printDPTable(text1, text2);
        
        String text3 = "aggtab";
        String text4 = "gxtxayb";
        System.out.println("\ntext1: " + text3 + ", text2: " + text4);
        System.out.println("LCS length: " + longestCommonSubsequence(text3, text4));
    }
}

Mürəkkəblik:

Time Complexity: O(m * n)
Space Complexity: O(m * n) - DP table üçün

4. Space Optimized (O(n) Space)

Koda bax

public class LCSOptimized {
    
    public static int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        
        // Use only two rows
        int[] prev = new int[n + 1];
        int[] curr = new int[n + 1];
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    curr[j] = prev[j - 1] + 1;
                } else {
                    curr[j] = Math.max(prev[j], curr[j - 1]);
                }
            }
            
            // Swap rows
            int[] temp = prev;
            prev = curr;
            curr = temp;
        }
        
        return prev[n];
    }
    
    // Ultra optimized: single array
    public static int longestCommonSubsequenceSingleArray(String text1, String text2) {
        // Make sure text2 is shorter
        if (text1.length() < text2.length()) {
            return longestCommonSubsequenceSingleArray(text2, text1);
        }
        
        int n = text2.length();
        int[] dp = new int[n + 1];
        
        for (int i = 1; i <= text1.length(); i++) {
            int prev = 0; // dp[i-1][j-1]
            
            for (int j = 1; j <= n; j++) {
                int temp = dp[j];
                
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[j] = prev + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
                
                prev = temp;
            }
        }
        
        return dp[n];
    }
    
    public static void main(String[] args) {
        System.out.println("LCS (Space Optimized):");
        
        String text1 = "abcde";
        String text2 = "ace";
        System.out.println("text1: " + text1 + ", text2: " + text2);
        System.out.println("LCS length: " + longestCommonSubsequence(text1, text2));
        
        String text3 = "aggtab";
        String text4 = "gxtxayb";
        System.out.println("\ntext1: " + text3 + ", text2: " + text4);
        System.out.println("LCS length: " + longestCommonSubsequence(text3, text4));
        
        // Performance test
        String long1 = "ABCDGH".repeat(100);
        String long2 = "AEDFHR".repeat(100);
        long startTime = System.currentTimeMillis();
        int result = longestCommonSubsequence(long1, long2);
        long endTime = System.currentTimeMillis();
        System.out.println("\nLong strings test: " + result);
        System.out.println("Vaxt: " + (endTime - startTime) + " ms");
    }
}

Mürəkkəblik:

Time Complexity: O(m * n)
Space Complexity: O(min(m, n)) - Yalnız bir və ya iki sətir

5. LCS String Reconstruction

Koda bax

public class LCSWithString {
    
    // Return the actual LCS string, not just length
    public static String longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        
        // Create DP table
        int[][] dp = new int[m + 1][n + 1];
        
        // Fill DP table
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        // Reconstruct LCS string
        StringBuilder lcs = new StringBuilder();
        int i = m, j = n;
        
        while (i > 0 && j > 0) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                lcs.append(text1.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }
        
        return lcs.reverse().toString();
    }
    
    // Return all LCS strings (there can be multiple)
    public static void printAllLCS(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        
        int[][] dp = new int[m + 1][n + 1];
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        System.out.println("All LCS strings:");
        findAllLCS(text1, text2, m, n, dp, "");
    }
    
    private static void findAllLCS(String s1, String s2, int i, int j, 
                                   int[][] dp, String current) {
        if (i == 0 || j == 0) {
            System.out.println(new StringBuilder(current).reverse().toString());
            return;
        }
        
        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
            findAllLCS(s1, s2, i - 1, j - 1, dp, current + s1.charAt(i - 1));
        } else {
            if (dp[i - 1][j] >= dp[i][j - 1]) {
                findAllLCS(s1, s2, i - 1, j, dp, current);
            }
            if (dp[i][j - 1] >= dp[i - 1][j]) {
                findAllLCS(s1, s2, i, j - 1, dp, current);
            }
        }
    }
    
    public static void main(String[] args) {
        System.out.println("LCS String Reconstruction:");
        
        String text1 = "abcde";
        String text2 = "ace";
        System.out.println("text1: " + text1 + ", text2: " + text2);
        System.out.println("LCS: " + longestCommonSubsequence(text1, text2));
        
        String text3 = "aggtab";
        String text4 = "gxtxayb";
        System.out.println("\ntext1: " + text3 + ", text2: " + text4);
        System.out.println("LCS: " + longestCommonSubsequence(text3, text4));
        
        System.out.println("\nExample with multiple LCS:");
        printAllLCS("ABCBDAB", "BDCABA");
    }
}

Mürəkkəblik:

Time Complexity: O(m * n)
Space Complexity: O(m * n) - DP table və rekonstruksiya üçün

Variantlar və Əlaqəli Problemlər

Koda bax

public class LCSVariants {
    
    // 1. Longest Common Substring (ardıcıl olmalıdır)
    public static int longestCommonSubstring(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        int maxLen = 0;
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    maxLen = Math.max(maxLen, dp[i][j]);
                } else {
                    dp[i][j] = 0; // Reset if not matching
                }
            }
        }
        
        return maxLen;
    }
    
    // 2. Shortest Common Supersequence
    public static int shortestCommonSupersequence(String str1, String str2) {
        int lcsLength = LCSTabulation.longestCommonSubsequence(str1, str2);
        return str1.length() + str2.length() - lcsLength;
    }
    
    // 3. Minimum Deletions to Make Two Strings Equal
    public static int minDeletions(String str1, String str2) {
        int lcsLength = LCSTabulation.longestCommonSubsequence(str1, str2);
        return (str1.length() - lcsLength) + (str2.length() - lcsLength);
    }
    
    // 4. Longest Palindromic Subsequence
    public static int longestPalindromicSubsequence(String s) {
        String reversed = new StringBuilder(s).reverse().toString();
        return LCSTabulation.longestCommonSubsequence(s, reversed);
    }
    
    // 5. LCS of Three Strings
    public static int lcsOfThree(String s1, String s2, String s3) {
        int m = s1.length();
        int n = s2.length();
        int o = s3.length();
        
        int[][][] dp = new int[m + 1][n + 1][o + 1];
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                for (int k = 1; k <= o; k++) {
                    if (s1.charAt(i-1) == s2.charAt(j-1) && 
                        s2.charAt(j-1) == s3.charAt(k-1)) {
                        dp[i][j][k] = dp[i-1][j-1][k-1] + 1;
                    } else {
                        dp[i][j][k] = Math.max(dp[i-1][j][k],
                                      Math.max(dp[i][j-1][k], dp[i][j][k-1]));
                    }
                }
            }
        }
        
        return dp[m][n][o];
    }
    
    public static void main(String[] args) {
        System.out.println("LCS Variants:");
        
        System.out.println("\n1. Longest Common Substring:");
        System.out.println("'abcde' and 'abfce': " + 
            longestCommonSubstring("abcde", "abfce"));
        
        System.out.println("\n2. Shortest Common Supersequence:");
        System.out.println("'geek' and 'eke': " + 
            shortestCommonSupersequence("geek", "eke"));
        
        System.out.println("\n3. Minimum Deletions:");
        System.out.println("'sea' and 'eat': " + 
            minDeletions("sea", "eat"));
        
        System.out.println("\n4. Longest Palindromic Subsequence:");
        System.out.println("'bbbab': " + 
            longestPalindromicSubsequence("bbbab"));
        
        System.out.println("\n5. LCS of Three Strings:");
        System.out.println("'geeks', 'geeksfor', 'geeksforgeeks': " + 
            lcsOfThree("geeks", "geeksfor", "geeksforgeeks"));
    }
}

Performance Müqayisəsi

Koda bax

public class LCSComparison {
    
    public static void comparePerformance() {
        String[][] testCases = {
            {"abc", "abc"},
            {"abcde", "ace"},
            {"aggtab", "gxtxayb"},
            {"ABCDGH".repeat(10), "AEDFHR".repeat(10)},
            {"ABCDGH".repeat(50), "AEDFHR".repeat(50)}
        };
        
        System.out.println("Performance Müqayisəsi:");
        System.out.println("Test\tNaive\t\tMemo\t\tTabulation\tOptimized");
        
        for (int t = 0; t < testCases.length; t++) {
            String s1 = testCases[t][0];
            String s2 = testCases[t][1];
            System.out.print((t + 1) + "\t");
            
            // Naive (only for small strings)
            if (s1.length() <= 10) {
                long start = System.nanoTime();
                LCSNaive.longestCommonSubsequence(s1, s2);
                long end = System.nanoTime();
                System.out.print((end - start) / 1000 + "μs\t\t");
            } else {
                System.out.print("Too slow\t");
            }
            
            // Memoization
            long start = System.nanoTime();
            LCSMemoization.longestCommonSubsequence(s1, s2);
            long end = System.nanoTime();
            System.out.print((end - start) / 1000 + "μs\t\t");
            
            // Tabulation
            start = System.nanoTime();
            LCSTabulation.longestCommonSubsequence(s1, s2);
            end = System.nanoTime();
            System.out.print((end - start) / 1000 + "μs\t\t");
            
            // Optimized
            start = System.nanoTime();
            LCSOptimized.longestCommonSubsequence(s1, s2);
            end = System.nanoTime();
            System.out.print((end - start) / 1000 + "μs");
            
            System.out.println();
        }
    }
    
    public static void main(String[] args) {
        comparePerformance();
    }
}

Müsahibə Sualları

1. Əsas LCS Problemi

Sual: İki sətirin ən uzun ümumi alt-ardıcıllığının uzunluğunu tapın. LeetCode: Problem 1143 - Longest Common Subsequence

2. LCS String-ini Tapmaq

Sual: Yalnız uzunluq deyil, konkret LCS string-ini qaytarın. Cavab: Backtracking ilə DP table-dən reconstruct etmək

3. Longest Common Substring

Sual: Ən uzun ümumi substring (ardıcıl) tapın. Cavab: dp[i][j] = 0 if mismatch (LCS-dən fərqi budur)

4. Shortest Common Supersequence

Sual: Hər iki sətiri əhatə edən ən qısa sətiri tapın. LeetCode: Problem 1092 - Shortest Common Supersequence

5. Edit Distance

Sual: Bir sətri digərinə çevirmək üçün minimum əməliyyat sayı. LeetCode: Problem 72 - Edit Distance (LCS pattern istifadə edir)

LeetCode Problemləri

1143. Longest Common Subsequence - https://leetcode.com/problems/longest-common-subsequence/ (Əsas problem)
1092. Shortest Common Supersequence - https://leetcode.com/problems/shortest-common-supersequence/ (LCS istifadə edir)
72. Edit Distance - https://leetcode.com/problems/edit-distance/ (Oxşar DP pattern)
583. Delete Operation for Two Strings - https://leetcode.com/problems/delete-operation-for-two-strings/ (LCS əsaslıdır)
516. Longest Palindromic Subsequence - https://leetcode.com/problems/longest-palindromic-subsequence/ (LCS(s, reverse(s)))

Real-World Tətbiqləri

Version Control (Git): Diff və merge əməliyyatları
Bioinformatics: DNA ardıcıllığının müqayisəsi
Plagiarism Detection: Mətn oxşarlığının yoxlanması
File Comparison: Fayl dəyişikliklərinin müəyyən edilməsi
Data Compression: Pattern recognition və compression

Optimizasiya Məsləhətləri

Space optimization: O(min(m,n)) space-ə endirmək mümkündür
Qısa sətri ikinci parametr: Space optimization üçün
Early termination: Maksimum mümkün uzunluq əldə edilibsə
Hirschberg's algorithm: O(min(m,n)) space ilə string reconstruction
Parallel processing: Diaqonal hesablamalar paralelləşdirilə bilər

Əlaqəli Problemlər

Edit Distance (Levenshtein Distance)
Longest Palindromic Subsequence
Shortest Common Supersequence
Minimum ASCII Delete Sum
Uncrossed Lines
Distinct Subsequences

Problem Təsviri​

Müxtəlif Yanaşmalar​

1. Sadə Rekursiya (Naive Approach)​

2. Memoization (Top-Down DP)​

3. Tabulation (Bottom-Up DP)​

4. Space Optimized (O(n) Space)​

5. LCS String Reconstruction​

Variantlar və Əlaqəli Problemlər​

Performance Müqayisəsi​

Müsahibə Sualları​

1. Əsas LCS Problemi​

2. LCS String-ini Tapmaq​

3. Longest Common Substring​

4. Shortest Common Supersequence​

5. Edit Distance​

LeetCode Problemləri​

Real-World Tətbiqləri​

Optimizasiya Məsləhətləri​

Əlaqəli Problemlər​

Problem Təsviri

Müxtəlif Yanaşmalar

1. Sadə Rekursiya (Naive Approach)

2. Memoization (Top-Down DP)

3. Tabulation (Bottom-Up DP)

4. Space Optimized (O(n) Space)

5. LCS String Reconstruction

Variantlar və Əlaqəli Problemlər

Performance Müqayisəsi

Müsahibə Sualları

1. Əsas LCS Problemi

2. LCS String-ini Tapmaq

3. Longest Common Substring

4. Shortest Common Supersequence

5. Edit Distance

LeetCode Problemləri

Real-World Tətbiqləri

Optimizasiya Məsləhətləri

Əlaqəli Problemlər