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

  1. String s: A non-empty string containing only the characters '*' and '|'.
  2. 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;
    }
}

Author Of article : Prashant Mishra Read full article