Do it for FUN | SUMFIのBlog

[LeetCode] Longest Unequal Adjacent Groups Subsequence II 2023-10-15|PSLeetCode|Problem Solving-Hash Table

2901. Longest Unequal Adjacent Groups Subsequence II

You are given an integer n, a 0-indexed string array words, and a 0-indexed array groups, both arrays having length n.

The hamming distance between two strings of equal length is the number of positions at which the corresponding characters are different.

You need to select the longest subsequence from an array of indices [0, 1, ..., n - 1], such that for the subsequence denoted as [i0, i1, ..., ik - 1] having length k, the following holds:

For adjacent indices in the subsequence, their corresponding groups are unequal, i.e., groups[ij] != groups[ij + 1], for each j where 0 < j + 1 < k.

words[ij] and words[ij + 1] are equal in length, and the hamming distance between them is 1, where 0 < j + 1 < k, for all indices in the subsequence.

Return a string array containing the words corresponding to the indices (in order) in the selected subsequence. If there are multiple answers, return any of them.

A subsequence of an array is a new array that is formed from the original array by deleting some (possibly none) of the elements without disturbing the relative positions of the remaining elements.

Note: strings in words may be unequal in length.

[LeetCode] Longest Unequal Adjacent Groups Subsequence I 2023-10-15|PSLeetCode|Problem Solving-Hash Table

2900. Longest Unequal Adjacent Groups Subsequence I

You are given an integer n, a 0-indexed string array words, and a 0-indexed binary array groups, both arrays having length n.

You need to select the longest subsequence from an array of indices [0, 1, ..., n - 1], such that for the subsequence denoted as [i0, i1, ..., ik - 1] having length k, groups[ij] != groups[ij + 1], for each j where 0 < j + 1 < k.

Return a string array containing the words corresponding to the indices (in order) in the selected subsequence. If there are multiple answers, return any of them.

A subsequence of an array is a new array that is formed from the original array by deleting some (possibly none) of the elements without disturbing the relative positions of the remaining elements.

Note: strings in words may be unequal in length.

[LeetCode] Last Visited Integers 2023-10-15|PSLeetCode|Problem Solving

2899. Last Visited Integers

Given a 0-indexed array of strings words where words[i] is either a positive integer represented as a string or the string "prev".

Start iterating from the beginning of the array; for every "prev" string seen in words, find the last visited integer in words which is defined as follows:

Let k be the number of consecutive "prev" strings seen so far (containing the current string). Let nums be the 0-indexed array of integers seen so far and nums_reverse be the reverse of nums, then the integer at (k - 1)th index of nums_reverse will be the last visited integer for this "prev".

If k is greater than the total visited integers, then the last visited integer will be -1.

Return an integer array containing the last visited integers.

[LeetCode] Count of Sub-Multisets With Bounded Sum 2023-10-15|PSLeetCode|Problem Solving-Dynamic Programming-Combinatorics-Sliding Window-Knapsack-Monotonic Deque

2902. Count of Sub-Multisets With Bounded Sum

You are given a 0-indexed array nums of non-negative integers, and two integers l and r.

Return the count of sub-multisets within nums where the sum of elements in each subset falls within the inclusive range of [l, r].

Since the answer may be large, return it modulo 109 + 7.

A sub-multiset is an unordered collection of elements of the array in which a given value x can occur 0, 1, ..., occ[x] times, where occ[x] is the number of occurrences of x in the array.

Note that:

Two sub-multisets are the same if sorting both sub-multisets results in identical multisets.

The sum of an empty multiset is 0.