# Count the number of distinct subarrays

I want to determine the number of distinct subarrays that can form having at most a given number of odd elements. Two subarrays are distinct if they differ at even one position. The subarray is a contiguous position of an array. Please give some suggestions to improve the time and space complexity.

Exp1:
Input: nums = [1, 2, 3, 4], k = 1
Output: 8
Explanation: [1], [2], [3], [4], [1, 2], [2, 3], [3, 4], [2, 3, 4]

Exp2:
Input: nums = [3, 2, 3, 4], k = 1
Output: 7
Explanation: [3], [2], [4], [3, 2], [2, 3], [3, 4], [2, 3, 4]
Note we did not count [3, 2, 3] since it has more than k odd elements.

Exp3:
Input: nums = [3, 2, 3, 2], k = 1
Output: 5
Explanation: [3], [2], [3, 2], [2, 3], [2, 3, 2]
[3], [2], [3, 2] - duplicates
[3, 2, 3], [3, 2, 3, 2] - more than k odd elements


class result {

static int numberOfSubarrays(int[] numbers, int k) {
if(k == 0) return 0;

boolean [] IsOdd = new boolean [numbers.length];

for(int i = 0; i < numbers.length; i++){
IsOdd[i] = numbers[i] %2 != 0;
}

HashSet<String> subs = new HashSet<String>();

for(int i = 0; i < numbers.length; i++){
StringBuilder sb = new StringBuilder();
int oddCount = 0;

for(int j = i; j < numbers.length; j++){
if(IsOdd[j]){
oddCount++;
if(oddCount > k){
break;
}
}
sb.append(numbers[j] + " ");
}
}
return subs.size();
}

}


Welcome to Stack Review, the first thing I see in your code is:

class result { ..your code }


Instead of result you should use Result as a classname because as specified in java_naming_conventions : Class names should be nouns, in mixed case with the first letter of each internal word capitalized.

The second thing I see in your code is:

HashSet<String> subs = new HashSet<String>();


Better to declare instead Set<String> subs = new HashSet<String>(); that guarantees more flexibility in case you want to use another implementation of theSet interface.

About performance, briefly you have a for loop where you instantiate a new StringBuilder object at every iteration like below:

for(int i = 0; i < numbers.length; i++){
StringBuilder sb = new StringBuilder();
...other instructions
sb.append(numbers[j] + " ");
}


There is a debated alternative to this scenario corresponding to instantiate one single StringBuilder object with a fixed capacity and resetting its length at every iteration of the loop with the StringBuilder.setLength method like below:

StringBuilder sb = new StringBuilder(Arrays.toString(numbers).length());
for(int i = 0; i < numbers.length; i++){
...other instructions
sb.setLength(0);
}



For every testcase I set the capacity of the StringBuilder object to the length of the String representation of the initial array like [1, 2, 3, 4] that is the maximal string length the StringBuilder will contain.

Update after @TorbenPutkonen comment : better to use StringBuilder.setLength(0) at the beginning of the loop to improve readibility of the code, so the reader has a clear vision of the state of the StringBuilder at the beginning and not at the end.

• When used in a loop, the preference should be to reset the StringBuilder with setLength(0) before it's use begins instead of after it has been used. This way the reader does not have to go through all the code to find out what the state of the StringBuilder is at the beginning of the loop. Commented Mar 31, 2021 at 5:48
• @TorbenPutkonen - You are completely right, thank you for the advice. Commented Mar 31, 2021 at 7:27
• @dariosicily if I do that, it will mess up the output. Commented Apr 2, 2021 at 10:34
• @wagaga I don't understand in which way it will mess up the output, I substituted the creation of one empty StringBuilder at every iteration with the creation of one StringBuilder that will be reset at every iteration. Commented Apr 2, 2021 at 10:59