Do it for FUN | SUMFIのBlog

[LeetCode] Maximum Deletions on a String 2022-10-02|PSLeetCode|Problem Solving-Dynamic Programming-Rolling Hash

You are given a string s consisting of only lowercase English letters. In one operation, you can:

Delete the entire string s, or

Delete the first i letters of s if the first i letters of s are equal to the following i letters in s, for any i in the range 1 <= i <= s.length / 2.

For example, if s = “ababc”, then in one operation, you could delete the first two letters of s to get “abc”, since the first two letters of s and the following two letters of s are both equal to “ab”.

Return the maximum number of operations needed to delete all of s.

[LeetCode] Number of Pairs Satisfying Inequality 2022-10-01|PSLeetCode|Fenwick Tree-Problem Solving

2426. Number of Pairs Satisfying Inequality

You are given two 0-indexed integer arrays nums1 and nums2, each of size n, and an integer diff. Find the number of pairs (i, j) such that:

0 <= i < j <= n - 1 and

nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff.

Return the number of pairs that satisfy the conditions.

[LeetCode] Bitwise XOR of All Pairings 2022-10-01|PSLeetCode|Problem Solving-Math-Bit Manipulation

2425. Bitwise XOR of All Pairings

You are given two 0-indexed arrays, nums1 and nums2, consisting of non-negative integers. There exists another array, nums3, which contains the bitwise XOR of all pairings of integers between nums1 and nums2 (every integer in nums1 is paired with every integer in nums2 exactly once).

Return the bitwise XOR of all integers in nums3.

[LeetCode] Longest Uploaded Prefix 2022-10-01|PSLeetCode|Problem Solving-Heap

2424. Longest Uploaded Prefix

You are given a stream of n videos, each represented by a distinct number from 1 to n that you need to “upload” to a server. You need to implement a data structure that calculates the length of the longest uploaded prefix at various points in the upload process.

We consider i to be an uploaded prefix if all videos in the range 1 to i (inclusive) have been uploaded to the server. The longest uploaded prefix is the maximum value of i that satisfies this definition.

Implement the LUPrefix class:

LUPrefix(int n) Initializes the object for a stream of n videos.

void upload(int video) Uploads video to the server.

int longest() Returns the length of the longest uploaded prefix defined above.