lcpz

// https://leetcode.com/problems/longest-palindromic-substring

class Solution {
public:
    string longestPalindrome(const string &s) { // Manacher's algorithm, O(n) time
        if (s.size() <= 1) return s;

        // insert a bogus char between chars, including outer boundaries
        string t = "|";
        for (auto ch : s) t += ch, t += "|";

lcpz

#include <iostream>
#include <string>
#include <math.h>
#include <boost/dynamic_bitset.hpp>

void print_subsets(const std::string &str) {
    std::cout << "[empty string]\n";

    const int n = str.size();

lcpz

#include <iostream>
#include <vector>
#include <stack>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

lcpz

// https://leetcode.com/problems/find-median-from-data-stream

class MedianFinder {
    priority_queue<int> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;
public:
    void addNum(int num) {
        if (maxHeap.empty() || maxHeap.top() >= num)
            maxHeap.push(num);
        else

lcpz

// https://leetcode.com/problems/implement-strstr

class Solution {
public:
    // Brute force, O((m - n) * n) worst and average case, O(n) best case
    int strStrNaive(const string& text, const string& pattern) {
        int m = text.size(), n = pattern.size();

        // be consistent with C/C++ strstr() and Java indexOf()
        if (!n) return 0;

lcpz

class Solution {
    int getPivotIndex(int& l, int& r) {
        return l + (r - l) / 2;
        //return l + rand() % (r - l + 1);
    }
    
    int partition(vector<int>& A, int& l, int& r) {
        int i = l, pivotIndex = getPivotIndex(l, r), pivot = A[pivotIndex];
        
        swap(A[pivotIndex], A[r]);

lcpz

// https://leetcode.com/problems/split-array-largest-sum

// Same as https://www.codingninjas.com/codestudio/library/book-allocation-problem

class Solution {
public:
    /*
     * Let dp[i][j + 1] be the an optimal solution to the subproblem with i subarrays within
     * A[0..j]. Let sum[i][j] be the sum of the numbers in A[i..j]. Then:
     *

lcpz

// https://leetcode.com/problems/median-of-two-sorted-arrays

// https://www.youtube.com/watch?v=LPFhl65R7ww
// https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/2471/Very-concise-O(log(min(MN)))-iterative-solution-with-detailed-explanation

class Solution {
public:
    double findMedianSortedArrays(vector<int>& a1, vector<int>& a2) {
        if (a1.size() > a2.size()) swap(a1, a2); // ensure a1 is shorter

lcpz

// https://leetcode.com/problems/count-unique-characters-of-all-substrings-of-a-given-string

/*
 * # Brute force approach
 *
 * Generate all substrings, and count the unique chars in each.
 *
 * Time complexity: O(n^2) to generate all substrings, O(n) to count unique chars for
 * each. Total: O(n^3).
 *

lcpz

// https://leetcode.com/problems/merge-k-sorted-lists

/*
 * O(N log k) time and O(1) space, where N is the total number of nodes.
 *
 * # Explanation of the time complexity
 *
 * Let n be an upper bound on the number of nodes of each list.
 *
 * We iteratively merge pairs of lists as follows: