Day 57: Competitive Programming Journal

Date: November 22, 2024
Hello Everyone,

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

What I Did Today:
I focused on solving two problems: Partition a set into k subsets with equal sums (Backtracking) and Determine if a string contains all permutations of another string.

1. Partition a set into k subsets with equal sums (Backtracking):

Problem:
Given a set of numbers, partition them into k subsets with equal sum.

Explanation:

• Use backtracking to explore all possible partitions and check if the sum of k subsets equals the target sum.
• If the subsets match the required sum, return true; otherwise, return false.

Implementation:

bool canPartition(vector<int>& nums, int n, int k, int targetSum, vector<int>& subsets) {
    if (k == 0) return true;
    if (targetSum == 0) return canPartition(nums, n, k - 1, targetSum, subsets); 

    for (int i = 0; i < n; ++i) {
        if (subsets[i] + nums[n - 1] <= targetSum) {
            subsets[i] += nums[n - 1];
            if (canPartition(nums, n - 1, k, targetSum, subsets)) return true;
            subsets[i] -= nums[n - 1];
        }
    }

    return false;
}

bool partitionKSubsets(vector<int>& nums, int k) {
    int totalSum = accumulate(nums.begin(), nums.end(), 0);
    if (totalSum % k != 0) return false;

    vector<int> subsets(k, 0);
    int targetSum = totalSum / k;

    return canPartition(nums, nums.size(), k, targetSum, subsets);
}

2. Determine if a string contains all permutations of another string:

Problem:
Given two strings str1 and str2, determine if str1 contains all permutations of str2.

Explanation:

• Use character frequency counting and sliding window approach to verify if str1 contains all permutations of str2.
• If the frequency count of characters matches between the window size of str2 and str1, then return true.

Implementation:

bool containsPermutation(string str1, string str2) {
    if (str1.size() < str2.size()) return false;

    unordered_map<char, int> freqMap;
    for (char c : str2) freqMap[c]++;

    int left = 0, right = 0, count = str2.size();

    while (right < str1.size()) {
        if (freqMap.find(str1[right]) != freqMap.end()) {
            if (--freqMap[str1[right]] >= 0) count--;
        }

        if (count == 0) return true;

        if (right - left + 1 < str2.size()) right++;
        else {
            if (freqMap.find(str1[left]) != freqMap.end()) {
                if (++freqMap[str1[left]] > 0) count++;
            }
            left++;
            right++;
        }
    }

    return false;
}

Reflection:
Today's challenges required understanding backtracking and string manipulations. The partitioning problem was about ensuring equal partitioning into k subsets, which felt like a well-known subset sum variant. The permutation problem required character frequency checks, and the sliding window technique made it efficient. Both problems were insightful, giving more clarity on how backtracking and window-based approaches work for such problems.

Looking forward to tomorrow’s problems!