Number of balanced bracket subsequence of length 2 and 4 in Java
A balanced bracket subsequence is a sequence of properly nested brackets. The number of balanced bracket subsequences of a given length can be calculated using a combinatorial approach. For a 2nd-length balanced bracket subsequence, there are two possibilities, while for a 4th-length balanced bracket subsequence, there are six possibilities.
Example 1:
Input:{1,2,1,1,2,2}
Output: 14
Explanation: The code for the input {1, 2, 1, 1, 2, 2} generates two types of length 4 subsequences: 1 1 2 2 and 1 2 1 2. The first type involves finding pairs of opening brackets ("1") and calculating the number of closing brackets ("2") after the second opening bracket. The count of these subsequences is then multiplied by the total number of closing brackets, which is then divided by the number of "2"s after the second opening bracket. This results in 14 balanced bracket subsequences of length 4, resulting in the final output of 14.
Example 2:
Input: {1,2,1,2}
Output: 4
Explanation: The output for the input `{1, 2, 1, 2}` is divided into two subsequences: length 2 subsequences and length 4 subsequences. The length 2 subsequences consist of 2 opening brackets and 2 closing brackets, resulting in a total count of 2 * 2 = 4. The length 4 subsequences consist of 4 balanced bracket subsequences of length 4, with the final output being 4 = 4. This process helps to identify the most suitable subsequences for the input.
Using Naive Approach
The program `BalancedBracketSubsequences` calculates the number of ways to form balanced bracket subsequences using an array of integers representing opening and closing brackets. It initializes an array suff, iterates through it, and calculates the total number of ways `ss` by considering different combinations of opening and closing brackets.
Here’s the implementation of the Number of balanced bracket subsequence of lengths 2 and 4 using a naive approach:
FileName:BalancedBracketSubsequences.java
import java.util.*;
public class BalancedBracketSubsequences {
static void countWays(int[] a, int n) {
long[] suff = new long[n];
if (a[n - 1] == 2) suff[n - 1] = 1;
for (int i = n - 2; i >= 0; i--) {
if (a[i] == 2) suff[i] = suff[i + 1] + 1;
else suff[i] = suff[i + 1];
}
long ss = 0;
for (int i = 0; i < n; i++) {
if (a[i] == 1) ss += suff[i];
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (a[i] == 1 && a[j] == 1 && suff[j] >= 2) {
ss += (suff[j]) * (suff[j] - 1) / 2;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (a[i] == 1 && a[j] == 1 && (suff[i] - suff[j]) >= 1 && suff[j] >= 1) {
ss += (suff[i] - suff[j]) * suff[j];
}
}
}
System.out.println(ss);
}
public static void main(String[] args) {
int[] a = {1, 2, 1, 1, 2, 2};
int n = 6;
countWays(a, n);
}
}
Output:
14
Complexity analysis: The code has a time complexity of O(n^2) and a space complexity of O(n), with the suff array being the only additional data structure used. The quadratic time complexity in nested loops dominates the overall time complexity, while the space complexity is O(n). Optimizing the algorithm for better scalability is recommended for larger input sizes.
Using Optimized Approach
The code calculates the count of trailing 2's for each element in an integer array, then adds them to the sum for each '1' in the sequence. It iterates through pairs of '1's, considering the trailing 2's count, and returns the total count of ways to form balanced bracket subsequences.
Here’s the implementation of the Number of balanced bracket subsequence of lengths 2 and 4 using the Optimized approach:
FileName:BalancedBracketSubsequences.java
import java.util.Arrays;
public class BalancedBracketSubsequences {
public static void main(String[] args) {
int[] sequence = {1, 2, 1, 1, 2, 2};
int n = sequence.length;
System.out.println(countWays(sequence, n));
}
// Function to count the ways to form balanced bracket subsequences
static long countWays(int[] a, int n) {
// Initialize an array to store the count of trailing 2's for each element
long[] suff = new long[n];
// Check if the last element is 2
if (a[n - 1] == 2)
suff[n - 1] = 1;
// Calculate the count of trailing 2's for each element in the sequence
for (int i = n - 2; i >= 0; i--) {
if (a[i] == 2)
suff[i] = suff[i + 1] + 1;
else
suff[i] = suff[i + 1];
}
// Initialize a variable to store the sum of trailing 2's for each 1 in the sequence
long sumSuffix = 0;
// Calculate the sum of trailing 2's for each 1 in the sequence
for (int i = 0; i < n; i++) {
if (a[i] == 1)
sumSuffix += suff[i];
}
// Initialize the result with the sum of trailing 2's for each 1 in the sequence
long result = sumSuffix;
// Loop through pairs of 1's and calculate additional combinations
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (a[i] == 1 && a[j] == 1 && suff[j] >= 2) {
// Calculate additional combinations for pairs of 1's with sufficient trailing 2's
result += (suff[j]) * (suff[j] - 1) / 2;
}
}
}
// Loop through pairs of 1's and calculate more combinations based on trailing 2's
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (a[i] == 1 && a[j] == 1 && (suff[i] - suff[j]) >= 1 && suff[j] >= 1) {
// Calculate additional combinations based on the difference in trailing 2's
result += (suff[i] - suff[j]) * suff[j];
}
}
}
// Return the final result
return result;
}
}
Output:
14
Complexity analysis: The code has a time complexity of O(n^2) due to the initialization of the `suff` array and the iteration of all pairs in the sequence array. The space complexity is O(n) due to the suff array, which stores the count of trailing 2's for each element in the sequence. Optimizing the algorithm for better scalability is recommended.