Day 47: Competitive Programming Journal

Date: November 8, 2024
Hello Everyone,

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

What I Did Today:
I solved two problems: Find the length of the longest palindrome that can be built using letters from a string and Reverse a string using recursion.

1. Find the length of the longest palindrome that can be built using letters from a string:
Problem:
Given a string, find the length of the longest palindrome that can be constructed using its letters. Characters can appear in any order, but at most one character can have an odd frequency.

Explanation:

• Use a frequency count of the characters.
• Add all pairs of characters to the palindrome's length.
• If any characters have an odd frequency, one of them can be placed in the center of the palindrome.

Implementation:

int longestPalindrome(string s) {
    unordered_map<char, int> freq;
    for (char c : s) {
        freq[c]++;
    }

    int length = 0;
    bool oddFound = false;

    for (auto& [key, value] : freq) {
        length += (value / 2) * 2;
        if (value % 2 == 1) {
            oddFound = true;
        }
    }

    if (oddFound) length += 1;

    return length;
}

2. Reverse a string using recursion:
**Problem:
**Reverse a string using recursion without using any additional data structures.

Explanation:

• Swap the first and last characters of the string and recursively process the remaining substring.

Implementation:

void reverseString(string& s, int i, int j) {
    if (i >= j) return; 
    swap(s[i], s[j]);
    reverseString(s, i + 1, j - 1); 
}

Reflection:
Today's problems were straightforward but insightful. I enjoyed implementing the recursive reversal and learning how character frequencies contribute to constructing palindromes. Both were great exercises for logical thinking and recursion.

Stay tuned for more updates, and happy coding!