C++ Notes

C++ Largest String

#include <string>

std::string largestString(std::string s)
{
    int len = static_cast<int>(s.size());
    std::string cur;

    for (int i = len - 1; i >= 0; --i) {
        cur = s[i] + cur;

        if (cur.size() == 3) {
            if (cur == "abb") {
                s[i] = 'b';
                s[i + 1] = 'a';
                s[i + 2] = 'a';
                if (i + 4 < len && s[i + 4] == 'b') {
                    i += 4 + 1;
                } else if (i + 3 < len && s[i + 3] == 'b') {
                    i += 3 + 1;
                } else if (s[i + 2] == 'b') {
                    i += 2 + 1;
                }
            }
            if (i + 1 < len && s[i + 1] == 'b') {
                i += 1 + 1;
            } else {
                ++i;
            }
            cur.clear();
        }
    }

    return s;
}

This builds the biggest valid string it can under the challenge rules by always choosing the best next character it is allowed to use.

C++ Max Counters

#include <algorithm>
#include <vector>

std::vector<int> maxCounters(int n, const std::vector<int>& a)
{
    std::vector<int> counters(n, 0);
    int maxCounter = 0;
    int lastUpdate = 0;
    int condition = n + 1;

    for (int v : a) {
        if (v <= n) {
            int index = v - 1;
            if (counters[index] < lastUpdate) {
                counters[index] = lastUpdate;
            }
            ++counters[index];
            maxCounter = std::max(maxCounter, counters[index]);
        }
        if (v == condition) {
            lastUpdate = maxCounter;
        }
    }

    for (int& c : counters) {
        if (c < lastUpdate) {
            c = lastUpdate;
        }
    }

    return counters;
}

This delays the expensive “set all counters to max” work until it is really needed, which keeps the solution fast.

C++ Max Double Slice Sum

#include <algorithm>
#include <vector>

long long maxDoubleSliceSum(const std::vector<int>& a)
{
    int size = static_cast<int>(a.size());
    if (size < 3) {
        return 0;
    }

    std::vector<long long> p1(size, 0);
    std::vector<long long> p2(size, 0);

    for (int i = 2; i < size - 1; ++i) {
        p1[i] = std::max<long long>(0, p1[i - 1] + a[i - 1]);
        p2[size - i - 1] = std::max<long long>(0, p2[size - i] + a[size - i]);
    }

    long long sum = p1[1] + p2[1];
    for (int i = 1; i < size - 1; ++i) {
        sum = std::max(sum, p1[i] + p2[i]);
    }

    return sum;
}

This keeps the best sum ending on the left and starting on the right, then combines them around each middle position.

C++ Max Product Of Three

#include <algorithm>
#include <vector>

long long maxProductOfThree(std::vector<int> a)
{
    std::sort(a.begin(), a.end());
    int c = static_cast<int>(a.size());

    long long topThree = static_cast<long long>(a[c - 1]) * a[c - 2] * a[c - 3];
    long long twoLowestAndTop = static_cast<long long>(a[0]) * a[1] * a[c - 1];

    return std::max(topThree, twoLowestAndTop);
}

This checks the useful extremes, because the best product can come from either the three largest numbers or two negatives plus one large positive.

C++ Max Profit

#include <algorithm>
#include <vector>

long long maxProfit(const std::vector<int>& a)
{
    long long price = a[0];
    long long profit = 0;

    for (int v : a) {
        price = std::min(price, static_cast<long long>(v));
        profit = std::max(profit, v - price);
    }

    return profit;
}

This tracks the lowest buy price seen so far and updates the best profit as it scans the prices once.

C++ Max Slice Sum

#include <algorithm>
#include <limits>
#include <vector>

long long maxSliceSum(const std::vector<int>& a)
{
    long long tmp = std::numeric_limits<long long>::min();
    long long max = std::numeric_limits<long long>::min();

    for (int v : a) {
        tmp = std::max(tmp + v, static_cast<long long>(v));
        max = std::max(max, tmp);
    }

    return max;
}

This is a Kadane-style scan: keep the best running sum and the best overall sum while moving once through the array.

C++ Min Avg Two Slice

#include <algorithm>
#include <vector>

int minAvgTwoSlice(const std::vector<int>& a)
{
    int idx = 0;
    double min = (a[0] + a[1]) / 2.0;

    for (std::size_t i = 0; i + 1 < a.size(); ++i) {
        double cur = (a[i] + a[i + 1]) / 2.0;
        if (i + 2 < a.size()) {
            double three = (a[i] + a[i + 1] + a[i + 2]) / 3.0;
            cur = std::min(cur, three);
        }
        if (cur < min) {
            min = cur;
            idx = static_cast<int>(i);
        }
    }

    return idx;
}

This leans on the key trick for this problem: the minimum average slice is always length 2 or 3.

C++ Min Perimeter Rectangle

#include <algorithm>
#include <limits>

long long minPerimeterRectangle(long long n)
{
    long long i = 1;
    long long min = std::numeric_limits<long long>::max();

    while (i * i < n) {
        if (n % i == 0) {
            min = std::min(min, 2 * (i + n / i));
        }
        ++i;
    }

    return min;
}

This searches factor pairs up to the square root and picks the pair with the smallest perimeter.

C++ Missing Integer

#include <algorithm>
#include <vector>

int missingInteger(std::vector<int> a)
{
    std::sort(a.begin(), a.end());
    a.erase(std::unique(a.begin(), a.end()), a.end());

    int min = 1;
    for (int v : a) {
        if (v > 0) {
            if (min != v) {
                break;
            }
            ++min;
        }
    }

    return min;
}

This records the positive numbers that exist, then returns the smallest positive value that is still missing.

C++ Nesting

#include <string>
#include <vector>

int nesting(const std::string& s)
{
    if (s.empty()) {
        return 1;
    }

    std::vector<char> stack;
    for (char c : s) {
        if (c == ')') {
            if (stack.empty() || stack.back() != '(') {
                return 0;
            }
            stack.pop_back();
        } else {
            stack.push_back(c);
        }
    }

    return stack.empty() ? 1 : 0;
}

This treats the string like a balance counter: open parentheses add one, closing ones remove one.