DEV Community

Prashant Mishra
Prashant Mishra

Posted on

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

  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]]
Enter fullscreen mode Exit fullscreen mode

Output:

[0, 2, 3]
Enter fullscreen mode Exit fullscreen mode
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;
    }
}
Enter fullscreen mode Exit fullscreen mode

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Get started

Community matters

Top comments (0)

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay