Posted on Jan 18

Count (*) between pipes (|)

Problem Statement: Count Stars Between Pipes

Problem Description

You are given a string s consisting of two types of characters:

Pipes ('|'), representing dividers.
Stars ('*'), representing items.

Additionally, you are given a list of ranges a, where each range is represented as an array [i, j]. For each range, you need to count the number of stars ('*') that are enclosed between the first and last pipes within the range.

If there are no valid pairs of pipes within a range, the result for that range should be 0.

Input

String s: A non-empty string containing only the characters '*' and '|'.
2D Array a: A list of ranges, where each range is represented as an array [i, j].
- i and j (0-based indices) represent the starting and ending indices of the range (inclusive).

Output

Return an array of integers where each element corresponds to the count of stars ('*') enclosed between the first and last pipes ('|') for the respective range in a.

Constraints

1 <= s.length <= 10^5
1 <= a.length <= 10^4
0 <= i <= j < s.length
s contains only the characters '*' and '|'.

Example

Input:

s = "|**|*|*" a = [[0, 2], [0, 4], [1, 6]]

Output:

[0, 2, 3]

import java.util.*; import java.io.*; public class Main { public static void main(String[] args) { String s = "|**|*|*"; int a[][]={{3,5},{0,4}}; for(int i : find(s,a)){ System.out.println(i); } } public static int[] find(String s , int [][] a){ int prefix[] = new int[s.length()]; int left[] = new int[s.length()]; int right[] = new int[s.length()]; int leftPipe = -1; int count = 0; for(int i =0;i<s.length();i++){ if(s.charAt(i)=='|'){ leftPipe = i; } left[i] = leftPipe; if(s.charAt(i)=='*'){ count++; } prefix[i] = count; } int rightPipe = -1; for(int i =s.length()-1;i>=0;i-- ){ if(s.charAt(i)=='|'){ rightPipe = i; } right[i] = rightPipe; } int index = 0; int result[] = new int[a.length]; for(int range[] : a){ int i = range[0]; int j = range[1]; //since we have to find * between i and j //we have to find the nearest | after i and nearest | before j int l = right[i]; // nearest | after i, we can get in right[i] int r = left[j];// nearest pipe before j we can get in left[j] if(l!=-1 && r!=-1 && l<r){ // make sure the pipe indexes are valid result[index] = prefix[r]-prefix[l];// get the * count between the pipes } index++; } return result; } }