Day 45: Competitive Programming Journal

Date: November 6, 2024.
Hello Everyone,

Today marks Day 45 of my competitive programming journey, and I’m here to share my progress.

What I Did Today:
I worked on two problems: Check if a string can be rearranged to form a palindrome and Find the maximum difference between two elements in an array such that the larger element comes after the smaller one.

1. Check if a string can be rearranged to form a palindrome:
Problem:
Given a string, check if its characters can be rearranged to form a palindrome.

Explanation:

• A string can be rearranged into a palindrome if at most one character has an odd frequency.
• Use a frequency array or hash map to count the occurrences of each character.
• Check the number of characters with odd frequencies.

Implementation:

bool canFormPalindrome(const string& str) {
    unordered_map<char, int> freq;

    for (char ch : str) {
        freq[ch]++;
    }

    int oddCount = 0;
    for (auto& pair : freq) {
        if (pair.second % 2 != 0) {
            oddCount++;
        }
    }

    return oddCount <= 1;
}

2. Find the maximum difference between two elements in an array such that the larger element comes after the smaller one:

Problem:
Given an array, find the maximum difference between two elements such that the larger element appears after the smaller one.

Explanation:

• Traverse the array while keeping track of the minimum element seen so far.
• Calculate the difference between the current element and the minimum element, and update the maximum difference if needed.

Implementation:

int maxDifference(const vector<int>& arr) {
    int minElement = INT_MAX;
    int maxDiff = INT_MIN;

    for (int num : arr) {
        minElement = min(minElement, num);
        maxDiff = max(maxDiff, num - minElement);
    }

    return maxDiff;
}

Reflection:
Today’s problems offered a mix of logic and optimization. The first problem, involving string rearrangement for a palindrome, reinforced my understanding of frequency counts and conditions for palindromes. The second problem highlighted the importance of tracking minimum and maximum values dynamically while traversing an array.

Stay tuned for more updates, and as always, happy coding!