Given an array of strings arr[] and two integers l and r, the task is to find the number of times the given string str occurs in the array in the range [l, r] (1-based indexing). Note that the strings contain only lowercase letters.
Examples:
Input: arr[] = {“abc”, “def”, “abc”}, L = 1, R = 2, str = “abc”
Output: 1
Input: arr[] = {“abc”, “def”, “abc”}, L = 1, R = 3, str = “ghf”
Output: 0
Approach: The idea is to use an unordered_map to store the indices in which the ith string of array occurs. If the given string is not present in the map then answer is zero otherwise perform binary search on the indices of the given string present in the map, and find the number of occurrences of the string in the range [L, R].
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the number of occurrences ofint NumOccurrences(string arr[], int n, string str, int L, int R){ // To store the indices of strings in the array unordered_map<string, vector<int> > M; for (int i = 0; i < n; i++) { string temp = arr[i]; auto it = M.find(temp); // If current string doesn't // have an entry in the map // then create the entry if (it == M.end()) { vector<int> A; A.push_back(i + 1); M.insert(make_pair(temp, A)); } else { it->second.push_back(i + 1); } } auto it = M.find(str); // If the given string is not // present in the array if (it == M.end()) return 0; // If the given string is present // in the array vector<int> A = it->second; int y = upper_bound(A.begin(), A.end(), R) - A.begin(); int x = upper_bound(A.begin(), A.end(), L - 1) - A.begin(); return (y - x);}// Driver codeint main(){ string arr[] = { "abc", "abcabc", "abc" }; int n = sizeof(arr) / sizeof(string); int L = 1; int R = 3; string str = "abc"; cout << NumOccurrences(arr, n, str, L, R); return 0;} |
Java
import java.util.*;public class GFG { // Function to return the number of occurrences of a string // within a given range public static int numOccurrences(String[] arr, int n, String str, int L, int R) { // HashMap to store the indices of strings in the array Map<String, List<Integer>> stringIndices = new HashMap<>(); // Iterate through the array of strings for (int i = 0; i < n; i++) { String currentString = arr[i]; // Check if the current string already has an entry in the HashMap List<Integer> indices = stringIndices.get(currentString); if (indices == null) { // If not, create a new entry in the HashMap with the current // string as key indices = new ArrayList<>(); indices.add(i + 1); stringIndices.put(currentString, indices); } else { // If there is already an entry, add the current index to //the list of indices indices.add(i + 1); } } // Check if the given string is present in the HashMap List<Integer> indices = stringIndices.get(str); if (indices == null) { // If not, return 0 return 0; } // Sort the list of indices Collections.sort(indices); // Get the upper bound of the range (R) int upperBound = upperBound(indices, R); // Get the upper bound of the range (L-1) int lowerBound = upperBound(indices, L - 1); // Return the number of occurrences of the string within the given range return upperBound - lowerBound; } // Helper function to get the upper bound of a given value in a sorted list private static int upperBound(List<Integer> list, int value) { int left = 0; int right = list.size() - 1; while (left <= right) { int mid = (left + right) / 2; if (list.get(mid) <= value) { left = mid + 1; } else { right = mid - 1; } } return left; } public static void main(String[] args) { String[] arr = {"abc", "abcabc", "abc"}; int n = arr.length; int L = 1; int R = 3; String str = "abc"; System.out.println(numOccurrences(arr, n, str, L, R)); }} |
Python3
# Python implementation of the approachfrom bisect import bisect_right as upper_boundfrom collections import defaultdict# Function to return the number of occurrences ofdef numOccurences(arr: list, n: int, string: str, L: int, R: int) -> int: # To store the indices of strings in the array M = defaultdict(lambda: list) for i in range(n): temp = arr[i] # If current string doesn't # have an entry in the map # then create the entry if temp not in M: A = [] A.append(i + 1) M[temp] = A else: M[temp].append(i + 1) # If the given string is not # present in the array if string not in M: return 0 # If the given string is present # in the array A = M[string] y = upper_bound(A, R) x = upper_bound(A, L - 1) return (y - x)# Driver Codeif __name__ == "__main__": arr = ["abc", "abcabc", "abc"] n = len(arr) L = 1 R = 3 string = "abc" print(numOccurences(arr, n, string, L, R))# This code is contributed by# sanjeev2552 |
Javascript
// JavaScript code for implementation of the approach// Function to return the number of occurrences offunction numOccurences(arr, n, string, L, R) { // To store the indices of strings in the array let M = new Map(); for (let i = 0; i < n; i++) { let temp = arr[i]; // If current string doesn't // have an entry in the map // then create the entry if (!M.has(temp)) { let A = []; A.push(i + 1); M.set(temp, A); } else { M.get(temp).push(i + 1); } } // If the given string is not // present in the array if (!M.has(string)) { return 0; } // If the given string is present // in the array let A = M.get(string); let y = upper_bound(A, R); let x = upper_bound(A, L - 1); return (y - x);}// Driver Codelet arr = ["abc", "abcabc", "abc"];let n = arr.length;let L = 1;let R = 3;let string = "abc";console.log(numOccurences(arr, n, string, L, R));// Function to find the upper boundfunction upper_bound(arr, x) { let l = 0; let r = arr.length; while (l < r) { let mid = Math.floor((l + r) / 2); if (arr[mid] <= x) { l = mid + 1; } else { r = mid; } } return l;}// contributed by adityasharmadev01 |
C#
using System;using System.Collections.Generic;using System.Linq;class Gfg{ static int NumOccurrences(string[] arr, int n, string str, int L, int R) { // To store the indices of strings in the array Dictionary<string, List<int>> M = new Dictionary<string, List<int>>(); for (int i = 0; i < n; i++) { string temp = arr[i]; if (M.TryGetValue(temp, out List<int> A)) { A.Add(i + 1); } else { A = new List<int>() { i + 1 }; M[temp] = A; } } if (M.TryGetValue(str, out List<int> indices)) { // If the given string is present in the array int y = indices.BinarySearch(R + 1); if (y < 0) y = ~y; int x = indices.BinarySearch(L); if (x < 0) x = ~x; return y - x; } else { // If the given string is not present in the array return 0; } } static void Main(string[] args) { string[] arr = { "abc", "abcabc", "abc" }; int n = arr.Length; int L = 1; int R = 3; string str = "abc"; Console.WriteLine(NumOccurrences(arr, n, str, L, R)); }} |
Output:
2
Time Complexity: O(N),
Auxiliary Space: O(N)
Another Approach:-
- As we have tp find the occurance of given string in range [l,r].
- We can just traverse the array from l to r, and can match each string with given string.
- If both matched then increase the count by 1.
- In the last return the count.
Implementation:-
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the number of occurrences ofint NumOccurrences(string arr[], int n, string str, int L, int R){ //variable to store answer int count=0; //iteration over array from l to r, 1-based indexing for (int i = L-1; i < R; i++) { //if string matched if(arr[i]==str)count++; } return count;}// Driver codeint main(){ string arr[] = { "abc", "abcabc", "abc" }; int n = sizeof(arr) / sizeof(string); int L = 1; int R = 3; string str = "abc"; cout << NumOccurrences(arr, n, str, L, R); return 0;}//code contributed by shubhamrajput6156 |
Java
import java.util.Arrays;class Main { // Function to return the number of occurrences of static int numOccurrences(String arr[], int n, String str, int L, int R) { // variable to store answer int count = 0; // iteration over array from l to r, 1-based indexing for (int i = L - 1; i < R; i++) { // if string matched if (arr[i].equals(str)) { count++; } } return count; } // Driver code public static void main(String[] args) { String arr[] = { "abc", "abcabc", "abc" }; int n = arr.length; int L = 1; int R = 3; String str = "abc"; System.out.println(numOccurrences(arr, n, str, L, R)); }} |
Python3
# Python implementation of the approachdef NumOccurrences(arr, n, str, L, R): # variable to store answer count = 0 # iteration over array from l to r, 1-based indexing for i in range(L-1, R): # if string matched if arr[i] == str: count += 1 return count# Driver codeif __name__ == '__main__': arr = ["abc", "abcabc", "abc"] n = len(arr) L = 1 R = 3 str = "abc" print(NumOccurrences(arr, n, str, L, R)) |
C#
using System;class MainClass { // Function to return the number of occurrences of static int NumOccurrences(string[] arr, int n, string str, int L, int R) { // variable to store answer int count = 0; // iteration over array from l to r, 1-based indexing for (int i = L - 1; i < R; i++) { // if string matched if (arr[i] == str) { count++; } } return count; } // Driver code public static void Main(string[] args) { string[] arr = { "abc", "abcabc", "abc" }; int n = arr.Length; int L = 1; int R = 3; string str = "abc"; Console.WriteLine(NumOccurrences(arr, n, str, L, R)); }} |
Javascript
// JavaScript implementation of the approachfunction NumOccurrences(arr, n, str, L, R) { // variable to store answer let count = 0; // iteration over array from l to r, 1-based indexing for (let i = L - 1; i < R; i++) { // if string matched if (arr[i] === str) { count += 1; } } return count;}// Driver codelet arr = ["abc", "abcabc", "abc"];let n = arr.length;let L = 1;let R = 3;let str = "abc";console.log(NumOccurrences(arr, n, str, L, R)); |
Output
2
Time Complexity:- O(N)
Space Complexity:- O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
