Question

Give a binary string s, return the number of non-empty substrings that have the same number of 0‘s and 1‘s, and all the 0‘s and all the 1‘s in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

Question

An array is said to be analogous to the secret array if all of the following conditions are true:
• The length of the array is equal to the length of the secret array.
• Each integer in the array lies in the interval [lowerBound, upperBound].
• The difference between each pair of consecutive integers of the array must be equal to the difference between the respective pair of consecutive integers in the secret array. In other words, let the secret array be [s[0], s[1],…, s[n-1]] and let the analogous array be [a[0], a[1],…, a[n-1]], then (a[i-1] - a[i]) must be equal to (s[i-1] - s[i]) for each i from 1 to n -1.

Given the value of integers lowerBound and upperBound, inclusive, and the array of differences between each pair of consecutive integers of the secret array, find the number of arrays that are analogous to the secret array. If there is no array analogous to the secret array, return 0.

For example:
consecutiveDifference = [-2, -1, -2, 5]
lowerBound = 3
upperBound = 10

Note that none of the values is out of the bound. All possible analogous arrays are:
[3, 5, 6, 8, 3]
[4, 6, 7, 9, 4]
[5, 7, 8, 10, 5]

Tha answer is 3.

Source: https://leetcode.com/discuss/interview-question/1332322/amazon-online-assessment-july-2021-secret-array

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public static int countAnalogousArrays(int[] consecutiveDifference, int lowerBound, int upperBound) {
    // parameter validation
    if (consecutiveDifference == null || consecutiveDifference.length < 1 || lowerBound > upperBound) {
        return 0;
    }
    int delta = 0, maxDelta = 0, minDelta = 0;
    for (int i = 0; i < consecutiveDifference.length; i++) {
        delta += consecutiveDifference[i];
        maxDelta = Math.max(maxDelta, delta);
        minDelta = Math.min(minDelta, delta);
    }
    int maxDiff = maxDelta - minDelta, boundGap = upperBound - lowerBound;
    // max difference exceeds bound gap
    if (maxDiff > boundGap) {
        return 0;
    }
    return boundGap - maxDiff;
}

Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems, so that we do not have to re-compute them when needed later.