Given a string S of size N consisting of lower case alphabets and an integer Q which represents the number of queries for S. Our task is to print the number of duplicate characters in the substring L to R for all the queries Q.
Note: 1 ?N ? 106 and 1 ? Q? 106
Examples:
Input :
S = “neveropen”, Q = 2
L = 1 R = 5
L = 4 R = 8
Output :
1
0
Explanation:
For the first query ‘e’ is the only duplicate character in S from range 1 to 5.
For the second query there is no duplicate character in S.Input :
S = “Geekyy”, Q = 1
L = 1 R = 6
Output :
2
Explanation:
For the first query ‘e’ and ‘y’ are duplicate characters in S from range 1 to 6.
Naive Approach:
The naive approach would be to maintain a frequency array of size 26, to store the count of each character. For each query, given a range [L, R] we will traverse substring S[L] to S[R] and keep counting the occurrence of each character. Now, if the frequency of any character is greater than 1 then we would add 1 to answer.
Efficient Approach:
To solve the above problem in an efficient way we will store the position of each character as it appears in the string in a dynamic array. For each given query we will iterate over all the 26 lower case alphabets. If the current letter is in the substring S[L: R] then the next element of the first element which is greater than or equal L to in the corresponding vector should exist and be less than or equal to R.
Diagram below shows how we store characters in the dynamic array:
Below is the implementation of the above approach:
CPP
// CPP implementation to Find the total// number of duplicate character in a// range L to R for Q number of queries in a string S#include <bits/stdc++.h>using namespace std;// Vector of vector to store// position of all characters// as they appear in stringvector<vector<int> > v(26);// Function to store position of each charactervoid calculate(string s){ for (int i = 0; i < s.size(); i++) { // Inserting position of each // character as they appear v[s[i] - 'a'].push_back(i); }}// Function to calculate duplicate// characters for Q queriesvoid query(int L, int R){ // Variable to count duplicates int duplicates = 0; // Iterate over all 26 characters for (int i = 0; i < 26; i++) { // Finding the first element which // is less than or equal to L auto first = lower_bound(v[i].begin(), v[i].end(), L - 1); // Check if first pointer exists // and is less than R if (first != v[i].end() && *first < R) { // Incrementing first pointer to check // if the next duplicate element exists first++; // Check if the next element exists // and is less than R if (first != v[i].end() && *first < R) duplicates++; } } cout << duplicates << endl;}// Driver Codeint main(){ string s = "neveropen"; int Q = 2; int l1 = 1, r1 = 5; int l2 = 4, r2 = 8; calculate(s); query(l1, r1); query(l2, r2); return 0;} |
Python3
# Python implementation to Find the total# number of duplicate character in a# range L to R for Q number of queries in a string Simport bisect# Vector of vector to store# position of all characters# as they appear in stringv = [[] for _ in range(26)]# Function to store position of each characterdef calculate(s: str) -> None: for i in range(len(s)): # Inserting position of each # character as they appear v[ord(s[i]) - ord('a')].append(i)# Function to calculate duplicate# characters for Q queriesdef query(L: int, R: int) -> None: # Variable to count duplicates duplicates = 0 # Iterate over all 26 characters for i in range(26): # Finding the first element which # is less than or equal to L first = bisect.bisect_left(v[i], L - 1) # Check if first pointer exists # and is less than R if (first < len(v[i]) and v[i][first] < R): # Incrementing first pointer to check # if the next duplicate element exists first += 1 # Check if the next element exists # and is less than R if (first < len(v[i]) and v[i][first] < R): duplicates += 1 print(duplicates)# Driver Codeif __name__ == "__main__": s = "neveropen" Q = 2 l1 = 1 r1 = 5 l2 = 4 r2 = 8 calculate(s) query(l1, r1) query(l2, r2)# This code is contributed by sanjeev2552 |
Java
// java implementation to Find the total// number of duplicate character in a// range L to R for Q number of queries in a string Simport java.util.ArrayList;import java.util.List;public class DuplicateCharacter { // List of List to store // position of all characters // as they appear in string static List<List<Integer> > v = new ArrayList<>(); // Function to store position of each character static void calculate(String s) { for (int i = 0; i < 26; i++) { v.add(new ArrayList<>()); } // Inserting position of each // character as they appear for (int i = 0; i < s.length(); i++) { v.get(s.charAt(i) - 'a').add(i); } } // Function to calculate duplicate // characters for Q queries static void query(int L, int R) { int duplicates = 0; for (int i = 0; i < 26; i++) { // Finding the first element which // is less than or equal to L int j = 0; while (j < v.get(i).size() && v.get(i).get(j) < L) { j++; } // Check if first pointer exists // and is less than R if (j < v.get(i).size() && v.get(i).get(j) < R) { // Incrementing first pointer to check // if the next duplicate element exists j++; // Check if the next element exists // and is less than R if (j < v.get(i).size() && v.get(i).get(j) < R) { duplicates++; } } } System.out.println(duplicates); } public static void main(String[] args) { String s = "neveropen"; int Q = 2; int l1 = 1, r1 = 5; int l2 = 4, r2 = 8; calculate(s); query(l1, r1); query(l2, r2); }} |
Javascript
// javascript code for the above approach// Function to find the index of // the first element in a sorted // array which is greater than or // equal to a given valuefunction bisect_left(arr, x) { let lo = 0, hi = arr.length; while (lo < hi) { let mid = Math.floor((lo + hi) / 2); if (arr[mid] < x) { lo = mid + 1; } else { hi = mid; } } return lo;}// Vector of array to store// position of all characters// as they appear in stringlet v = [...Array(26)].map(() => []);// Function to store position of each characterfunction calculate(s) { for (let i = 0; i < s.length; i++) { // Inserting position of each // character as they appear v[s.charCodeAt(i) - 'a'.charCodeAt(0)].push(i); }}// Function to calculate duplicate// characters for Q queriesfunction query(L, R) { // Variable to count duplicates let duplicates = 0; // Iterate over all 26 characters for (let i = 0; i < 26; i++) { // Finding the first element which // is less than or equal to L let first = bisect_left(v[i], L - 1); // Check if first pointer exists // and is less than R if (first < v[i].length && v[i][first] < R) { // Incrementing first pointer to check // if the next duplicate element exists first += 1; // Check if the next element exists // and is less than R if (first < v[i].length && v[i][first] < R) { duplicates += 1; } } } console.log(duplicates);}// Driver Codelet s = "neveropen";let Q = 2;let l1 = 1;let r1 = 5;let l2 = 4;let r2 = 8;calculate(s);query(l1, r1);query(l2, r2);// This code is contributed by princekumaras |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class DuplicateCharacter{ // List of List to store // position of all characters // as they appear in string static List<List<int>> v = new List<List<int>>(); // Function to store position of each character static void calculate(string s) { for (int i = 0; i < 26; i++) { v.Add(new List<int>()); } // Inserting position of each // character as they appear for (int i = 0; i < s.Length; i++) { v[s[i] - 'a'].Add(i); } } // Function to calculate duplicate // characters for Q queries static void query(int L, int R) { int duplicates = 0; for (int i = 0; i < 26; i++) { // Finding the first element which // is less than or equal to L int j = 0; while (j < v[i].Count && v[i][j] < L) { j++; } // Check if first pointer exists // and is less than R if (j < v[i].Count && v[i][j] < R) { // Incrementing first pointer to check // if the next duplicate element exists j++; // Check if the next element exists // and is less than R if (j < v[i].Count && v[i][j] < R) { duplicates++; } } } Console.WriteLine(duplicates); } public static void Main(string[] args) { string s = "neveropen"; int Q = 2; int l1 = 1, r1 = 5; int l2 = 4, r2 = 8; calculate(s); query(l1, r1); query(l2, r2); }}// This code is contributed by adityashatmfh |
Output:
1 0
Time Complexity: O( Q * 26 * log N)
Auxiliary Space: O(N)
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!
