Question

Given a string s, consider all duplicated substrings: (contiguous) substrings of s that occur 2 or more times. The occurrences may overlap.

Return any duplicated substring that has the longest possible length. If s does not have a duplicated substring, the answer is "".

Question

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.

Question

Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If there is no such subarray, return -1.

A subarray is a contiguous part of an array.

Question

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Question

Given a string s, find the length of the longest substring without repeating characters.

Question

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

• MinStack() initializes the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

Question

Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.

Question

You want to schedule a list of jobs in d days. Jobs are dependent (i.e To work on the ith job, you have to finish all the jobs j where 0 <= j < i).

You have to finish at least one task every day. The difficulty of a job schedule is the sum of difficulties of each day of the d days. The difficulty of a day is the maximum difficulty of a job done on that day.

You are given an integer array jobDifficulty and an integer d. The difficulty of the ith job is jobDifficulty[i].

Return the minimum difficulty of a job schedule. If you cannot find a schedule for the jobs return -1.

Traverse an array by groups

1
2
3
4
5
6

for (int i = 0; i < arr.length; i += interval) {
    for (int j = i; j < i + interval && j < arr.length; j++) {
        // do something
    }
    // do something
}

Calculate the submatrix sums fast

We can use a 2D prefix sum array. Each row of the 2D prefix sum array is a 1D prefix sum array for the corresponding row in the original matrix.

After initialization which takes $O(mn)$, calculating a submatrix sum takes $O(k)$, where k is the number of rows in the submatrix.

1
2
3
4
5
6
7
8

// given matrix[m][n]
int[][] prefixSum = new int[m][n];
// init
for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        // initialize each element in prefixSum[i]
    }
}

Question

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.