Today I have done Remove Palindromic Subsequences on leetcode and leetcode's November LeetCoding Challenge with cpp.

Remove Palindromic Subsequences

Description

Given a string s consisting only of letters 'a' and 'b'. In a single step you can remove one palindromic subsequence from s.

Return the minimum number of steps to make the given string empty.

A string is a subsequence of a given string, if it is generated by deleting some characters of a given string without changing its order.

A string is called palindrome if is one that reads the same backward as well as forward.

Example 1:

Input: s = "ababa"
Output: 1
Explanation: String is already palindrome

Example 2:

Input: s = "abb"
Output: 2
Explanation: "abb" -> "bb" -> "". 
Remove palindromic subsequence "a" then "bb".

Example 3:

Input: s = "baabb"
Output: 2
Explanation: "baabb" -> "b" -> "". 
Remove palindromic subsequence "baab" then "b".

Example 4:

Input: s = ""
Output: 0

Constraints:

• 0 <= s.length <= 1000
• s only consists of letters 'a' and 'b'

Solution

it's obvious that answer is 1 if and only if it's a palindrome already.

otherwise, the string must contain both a and b, so you could remove all a and then b, so 2 step is enough for any other string.

class Solution {
    bool isPalindrome(string s) {
        int len = s.size();
        for(int i = 0; 2*i < len; ++i) {
            if(s[i] != s[len-i-1]) return false;
        }
        return true;
    }
public:
    int removePalindromeSub(string s) {
        if(s.empty()) return 0;
        if(isPalindrome(s)) return 1;
        return 2;
    }
};

November LeetCoding Challenge 27

Description

Partition Equal Subset Sum

Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

Constraints:

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

Solution

I ignored the size of data and write a DFS solution, then it TLE

class Solution {
    bool dfs(vector<int>& nums, int curIndex, int curSum, int target) {
        if(curSum == target) return true;
        if(curIndex == nums.size()) return false;
        if(dfs(nums, curIndex+1, curSum+nums[curIndex], target)) return true;
        return dfs(nums, curIndex+1, curSum, target);
    }
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(auto i : nums) {
            sum += i;
        }
        if(sum & 1) return false;
        return dfs(nums, 0, 0, sum / 2);
    }
};

then I think that set is enough for this problem

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(auto i : nums) {
            sum += i;
        }
        if(sum & 1) return false;
        int target = sum >> 1;
        unordered_set<int> sums{0};
        unordered_set<int> nxt;
        for(auto i : nums) {
            for(auto s : sums) {
                if(s + i == target) return true;
                nxt.insert(s+i);
            }
            sums = nxt;
        }
        return false;
    }
};

time complexity of this solution is $O(n^2)$