📘 Print Longest Common Subsequence (LCS)

🔹 Approach (2 Steps)

✅ Step 1: Build DP Table

• Same as LCS length

✅ Step 2: Backtrack

• Start from (n, m)

• Move:

  • Diagonal → if characters match (take char)
  • Up / Left → based on max value

---

🔹 Full Code (C++)

string longestCommonSubsequence(string s1, string s2) {
    int n = s1.size(), m = s2.size();

    // Step 1: DP table
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(s1[i-1] == s2[j-1])
                dp[i][j] = 1 + dp[i-1][j-1];
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }

    // Step 2: Backtracking
    int i = n, j = m;
    string ans = "";

    while(i > 0 && j > 0){
        if(s1[i-1] == s2[j-1]){
            ans.push_back(s1[i-1]);
            i--;
            j--;
        }
        else if(dp[i-1][j] > dp[i][j-1]){
            i--;  // move up
        }
        else{
            j--;  // move left
        }
    }

    // reverse because we built it backwards
    reverse(ans.begin(), ans.end());
    return ans;
}

---

🔹 Example

👉 Input:

s1 = "AGGTAB"
s2 = "GXTXAYB"

👉 Output:

GTAB

---

🔹 Key Intuition 🧠

• Matching characters → part of LCS
• Otherwise → follow the path that gave max value

👉 Rule:

Match → take & go diagonal
Not match → go where value is larger

---

🔹 Complexity

• Time: O(n × m)
• Space: O(n × m)

---

🔹 Important Notes ⚠️

• Always reverse the answer
• This gives one valid LCS, not necessarily all
• Works for strings, arrays, etc.

---

🔥 Interview Tip

If asked:

“Print LCS”

Say confidently:

1. Build DP table
2. Backtrack from (n, m)

---

📘 Hirschberg’s Algorithm (LCS with O(m) space)

---

🔹 Why do we need it?

Normal LCS:

• Time: O(n*m)
• Space: O(n*m) ❌ (too large for big strings)

👉 Hirschberg reduces:

• Space → O(m) ✅
• Still prints LCS!

---

🔥 Core Idea (Divide & Conquer)

Instead of storing full DP table:

👉 Split string s1 into two halves:

s1 = left_half + right_half

Then:

1. Compute LCS length of left_half with all prefixes of s2
2. Compute LCS length of right_half (reversed) with all suffixes of s2
3. Find best split point k in s2
4. Recursively solve:

• (left_half, s2[0..k])
• (right_half, s2[k..m])

---

🧠 Visualization

s1 = ABC | DEF
s2 = GHIJKL

→ Find split k in s2
→ Solve:
   LCS(ABC, s2[0..k])
   +
   LCS(DEF, s2[k..end])

---

🔹 Key Trick

We only compute one row at a time → saves space

---

🔹 Helper Function (1D DP)

vector<int> lcsLength(string a, string b) {
    int n = a.size(), m = b.size();
    vector<int> prev(m+1, 0), curr(m+1, 0);

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(a[i-1] == b[j-1])
                curr[j] = 1 + prev[j-1];
            else
                curr[j] = max(prev[j], curr[j-1]);
        }
        prev = curr;
    }
    return prev;
}

---

🔹 Main Hirschberg Function

string hirschberg(string s1, string s2) {
    int n = s1.size(), m = s2.size();

    // base cases
    if(n == 0) return "";
    if(n == 1) {
        for(char c : s2) {
            if(c == s1[0]) return string(1, c);
        }
        return "";
    }

    int mid = n / 2;

    string left = s1.substr(0, mid);
    string right = s1.substr(mid);

    // forward LCS
    vector<int> L1 = lcsLength(left, s2);

    // reverse LCS
    reverse(right.begin(), right.end());
    string rev_s2 = s2;
    reverse(rev_s2.begin(), rev_s2.end());

    vector<int> L2 = lcsLength(right, rev_s2);

    // find partition k
    int k = 0, maxVal = 0;
    for(int j = 0; j <= m; j++){
        int val = L1[j] + L2[m - j];
        if(val > maxVal){
            maxVal = val;
            k = j;
        }
    }

    // divide and conquer
    string lcs_left = hirschberg(left, s2.substr(0, k));
    string lcs_right = hirschberg(s1.substr(mid), s2.substr(k));

    return lcs_left + lcs_right;
}

---

🔹 Complexity

Metric	Value
Time	O(n × m)
Space	O(m) ✅

---

🔥 Why it Works

• Avoids storing full DP table
• Uses only two rows at a time
• Reconstructs answer via recursion

---

⚠️ When to Use

👉 Use Hirschberg when:

• Strings are very large
• Memory is limited
• Interviewer asks “optimize space for printing LCS”

---

🧠 Interview Answer (Perfect 🔥)

If asked:

“Can you print LCS in O(m) space?”

Say:

“Yes, using Hirschberg’s Algorithm — a divide & conquer approach that computes LCS using 1D DP and reconstructs the sequence recursively.”

---

⚡ Final Intuition

Split → Solve → Combine
Use forward + reverse DP to find split point

---

If you want 🚀 next:

• Step-by-step dry run of Hirschberg
• Compare with normal DP visually
• Convert this into interview-ready explanation

Just tell me 👍