Day 51: Competitive Programming Journal

Date: November 14, 2024
Hello Everyone,

Today marks Day 51 of my competitive programming journey. Here's what I worked on today:

What I Did Today:
I solved two problems: Generate all balanced parentheses of length 2n and Find the longest common subsequence between two strings.

1. Generate all balanced parentheses of length 2n (Backtracking):
Problem:
Given a number n, generate all combinations of n pairs of balanced parentheses.

Explanation:

• Use recursion and backtracking to build the combinations.
• Track the number of open and close parentheses to ensure balance.

Implementation:

void generateParentheses(int open, int close, string current, vector<string>& result) {
    if (open == 0 && close == 0) {
        result.push_back(current);
        return;
    }

    if (open > 0) {
        generateParentheses(open - 1, close, current + "(", result);
    }

    if (close > open) {
        generateParentheses(open, close - 1, current + ")", result);
    }
}

vector<string> balancedParentheses(int n) {
    vector<string> result;
    generateParentheses(n, n, "", result);
    return result;
}

2. Find the longest common subsequence between two strings (Recursion):
Problem:
Given two strings, find the length of their longest common subsequence.

Explanation:

• Use recursion to compare characters from both strings.
• If characters match, add 1 and move to the next characters in both strings.
• Otherwise, explore both possibilities (skip one character in each string) and take the maximum length.

Implementation:

int longestCommonSubsequence(string s1, string s2, int i, int j) {
    if (i == s1.length() || j == s2.length()) {
        return 0;
    }

    if (s1[i] == s2[j]) {
        return 1 + longestCommonSubsequence(s1, s2, i + 1, j + 1);
    } else {
        return max(longestCommonSubsequence(s1, s2, i + 1, j),
                   longestCommonSubsequence(s1, s2, i, j + 1));
    }
}

Reflection:
Today’s problems were an excellent mix of recursion and backtracking. Generating balanced parentheses was particularly enjoyable as it required creative problem-solving. The longest common subsequence problem strengthened my understanding of recursion and string manipulations.

Stay tuned for more updates, and happy coding!