#3844 | Longest Almost-Palindromic Substring

Interesting problem for Strings ~ practice.

Problem link: https://leetcode.com/problems/longest-almost-palindromic-substring/description/

#LeetCode #BrainTeaser #Palindromes

3910. Count Connected Subgraphs with Even Node Sum | LC Hard

Topics: graphs, bitmasks, dfs, bfs

Problem link: https://leetcode.com/problems/count-connected-subgraphs-with-even-node-sum/

#LeetCode #Daily

115. Distinct Subsequences | LC Hard

My hardcoded solution 😅 (backward dp + combinatorics) -> https://pastebin.com/3F8jKYFT

Topics: dynamic programming, combinatorics, math

🔗 Problem link: https://leetcode.com/problems/distinct-subsequences/

#LeetCode #Daily #DP

1665. Minimum Initial Energy to Finish Tasks | LC Hard (actually: easy-medium ~ ACC rate 70%+)

Topics: greedy, sorting

My solution (Python): https://pastebin.com/ttvTFEqC

Problem Link: https://leetcode.com/problems/minimum-initial-energy-to-finish-tasks

#LeetCode #Daily

#1288 | Remove Covered Intervals

~ Задача на интервалы - классические задачи на интервью по распределению задач по процессам, планирование / оптимизация событий и т.д.

Problem Link: https://leetcode.com/problems/remove-covered-intervals/

Ещё на nFactorial подкасте был крутой разбор задачи по schedule-optimization от ex-Google DeepMind SWE - Adilet Zh.: https://youtu.be/gbgiFVFhGkc?si=3z3feGwhfNHOhJbo

#LeetCode #POTD #Intervals

Alice and Bob never disappoint :)

Hints (how I have solved):
* 10^6 * 10^3 -> 10^9 (so it's possible to iterate over all possible K values and in O(N) tc calculate max score diff);
* Use the sieve of Erotosthenes and Kadane's algorithm for calculating max score diff optimally;
* Don't forget to make (max_score_diff * min_k + MOD) % MOD to handle negative value cases;

🔗 Problem Link: https://leetcode.com/problems/divisible-game/

#LeetCode

+1 problem for practicing Dynamic Programming (DP)

~ DP is one of the most common algorithmic patterns you'll face in medium to hard interview questions.

🔗 Problem link: https://leetcode.com/problems/maximum-consistent-columns-in-a-grid

🔖 My solution with explanation: https://leetcode.com/problems/maximum-consistent-columns-in-a-grid/solutions/8401925/1d-dp-on-columns-with-validation-c-by-si-4osq

#LeetCode

Number of Unique XOR Triplets (I, II)

> Наткнулся на интересные задачки по битовой логике (давно не решал такие задачи):

Вам дается массив чисел nums и нужно посчитать уникальное количество XOR триплетов (i <= j <= k | nums[i] ^ nums[j] ^ nums[k]).

XOR logic gate основные правила:
* X ^ X ^ X = X
* X ^ X = 0

Q1: В первой версии задачи гарантируется, что числа это перестановки чисел от 1 до N. Но при этом размер массива N -> может быть до 10^5. То есть просто O(N^3) брутфорсом не получится решить :) ~ даже O(N^2) оптимизированное решение не пройдет -> есть красивое логическое решение за O(1).

Подсказки:
* Если числа гарантировано от 1 до N перестановка - то порядок чисел не имеет значение.
* До N <= 8 попробуйте перерешать вручную на бумаге битами :)

Q2: Во второй задаче уже числа могут быть любыми до <=1500, и также гарантируется, что размер массива будет до <=1500, то есть O(N^3) решение брутфорс тут не зайдет также -> займет кучу операций ~3.4 * 10^9 => TLE. Подсказка: но O(N^2) оптимизированное хэшсетами решение зайдет :)

Topics: Bit Manipulation, Math, Hashsets

Q1: https://leetcode.com/problems/number-of-unique-xor-triplets-i

Q2: https://leetcode.com/problems/number-of-unique-xor-triplets-ii

#LeetCode

Duval's Algorithm finds the lexicographically smallest rotation of a cyclic string in O(N) time, producing a unique canonical representation.

Key Steps:
1. Duplicate the string (s + s) so every rotation becomes a contiguous substring.
2. Compare two candidate rotations (i and j) character by character using offset k.
3. Skip impossible candidates whenever a mismatch is found:
> If rotation i is smaller, discard rotation j.
> Otherwise, discard rotation i.
4. Continue until only the best candidate remains.
5. Return the substring of length N starting from the smallest valid index.

> Problem for practice (#3999 - Hard): https://leetcode.com/problems/minimum-number-of-string-groups-through-transformations/
> Solution (explanation): https://leetcode.com/problems/minimum-number-of-string-groups-through-transformations/solutions/8421501/duvals-algorithm-for-getting-minimal-str-m3hj
+ Article: https://cp-algorithms.com/string/lyndon_factorization.html#implementation

#LeetCode

#4016: Maximum Area of Two Non-Overlapping Square Submatrices

~ Разбор интересной задачи из контеста LC Weekly #514 (Q3 - Medium*)

~ Суть задачи: дается бинарная матрица NxM (где 1 <= N, M <= 500) и значения каждой ячейки 0 или 1. Валидным квадратом считается любая квадратная подматрица состоящая только из однерок. Нужно найти максимальную площадь квадрата такую, что существут 2 непересекающихся квадрата внутри заданной матрицы.

~ Для эффективного решения за время `O(log(min(N, M)) x N x M)` применяется 2 подхода:
(1) двумерный массив префиксных сумм, чтобы за O(1) определять - это подматрица чисто из однерок или нет;
(2) бинарный поиск по возможным ответам используя тот факт, что если существует 2 непересекающихся валидных подматриц для площади X, то точно найдутся такие же валидные матрицы для площадей меньше X.

~ Ссылка на задачу: https://leetcode.com/problems/maximum-area-of-two-non-overlapping-square-submatrices
~ Подробный разбор задачи: https://leetcode.com/problems/maximum-area-of-two-non-overlapping-square-submatrices/solutions/8476870/2d-prefix-sum-binary-search-ologminn-m-n-dt1r

#leetcode #potd #favorite

#4032 | Longest Subarray With at Most K Distinct Prime Factors

Topics: prime factorization, 2 pointers

Problem Statement:

You are given an integer array numsconsisting of positive integers and an integer k. The prime factor set of a subarray is the union of the distinct prime factors of all its elements. Return the length of the longest subarray whose prime factor set contains at most k distinct prime factors. If no such subarray exists, return 0.

Input: nums = [7,6,10,12,11], k = 3
Output: 3
Explanation: longest subarray -> [6, 10, 12]
* 6: {2, 3}
* 10: {2, 5}
* 12: {2, 3}

Union set of prime factors: {2, 3, 5} and number of sets is at most K.

🔗 Link: https://leetcode.com/problems/longest-subarray-with-at-most-k-distinct-prime-factors/

#POTD #LeetCode