Given a string str. Now for every query consisting of two integer L and R, the task is to find the number of indices such that str[i] = str[i+1] and L ? i, i+1 ? R.
Examples:
Input: str = “ggggggggggg”, query[] = {{1, 2}, {1, 5}}
Output: 1 4
The answer is 1 for first query and 4 for second query.
The condition is true for all indices except the last one in each query.Input: str = “geeg”, query[] = {{0, 3}}
Output: 1
The condition is true only for i = 1.
Approach: Create a prefix array pref such that pref[i] holds the count of all the indices from 1 to i-1 such that str[i] = str[i+1]. Now for every query (L, R) the result will be pref[r] – pref[l].
Below is the implementation of the above approach:
C++
// C++ program to find substring with #include <bits/stdc++.h>using namespace std;// Function to create prefix arrayvoid preCompute(int n, string s, int pref[]){ pref[0] = 0; for (int i = 1; i < n; i++) { pref[i] = pref[i - 1]; if (s[i - 1] == s[i]) pref[i]++; }}// Function to return the result of the queryint query(int pref[], int l, int r){ return pref[r] - pref[l];}// Driver Codeint main(){ string s = "ggggggg"; int n = s.length(); int pref[n]; preCompute(n, s, pref); // Query 1 int l = 1; int r = 2; cout << query(pref, l, r) << endl; // Query 2 l = 1; r = 5; cout << query(pref, l, r) << endl; return 0;} |
Java
// Java program to find substring with import java.io.*;class GFG {// Function to create prefix arraystatic void preCompute(int n, String s, int pref[]){ pref[0] = 0; for (int i = 1; i < n; i++) { pref[i] = pref[i - 1]; if (s.charAt(i - 1)== s.charAt(i)) pref[i]++; }}// Function to return the result of the querystatic int query(int pref[], int l, int r){ return pref[r] - pref[l];}// Driver Code public static void main (String[] args) { String s = "ggggggg"; int n = s.length(); int pref[] = new int[n]; preCompute(n, s, pref); // Query 1 int l = 1; int r = 2; System.out.println( query(pref, l, r)); // Query 2 l = 1; r = 5; System.out.println(query(pref, l, r)); }}// This code is contributed by inder_verma.. |
Python3
# Python3 program for the given approach# Function to create prefix array def preCompute(n, s, pref): for i in range(1,n): pref[i] = pref[i - 1] if s[i - 1] == s[i]: pref[i] += 1 # Function to return the result of the query def query(pref, l, r): return pref[r] - pref[l] if __name__ == "__main__": s = "ggggggg" n = len(s) pref = [0] * n preCompute(n, s, pref) # Query 1 l = 1 r = 2 print(query(pref, l, r)) # Query 2 l = 1 r = 5 print(query(pref, l, r)) # This code is contributed by Rituraj Jain |
C#
// C# program to find substring with using System;class GFG {// Function to create prefix arraystatic void preCompute(int n, string s, int []pref){ pref[0] = 0; for (int i = 1; i < n; i++) { pref[i] = pref[i - 1]; if (s[i - 1]== s[i]) pref[i]++; }}// Function to return the result of the querystatic int query(int []pref, int l, int r){ return pref[r] - pref[l];}// Driver Code public static void Main () { string s = "ggggggg"; int n = s.Length; int []pref = new int[n]; preCompute(n, s, pref); // Query 1 int l = 1; int r = 2; Console.WriteLine( query(pref, l, r)); // Query 2 l = 1; r = 5; Console.WriteLine(query(pref, l, r)); }}// This code is contributed by inder_verma.. |
PHP
<?php // PHP program to find substring with // Function to create prefix arrayfunction preCompute($n, $s, &$pref){ $pref[0] = 0; for ($i = 1; $i < $n; $i++) { $pref[$i] = $pref[$i - 1]; if ($s[$i - 1] == $s[$i]) $pref[$i]++; }}// Function to return the result of the queryfunction query(&$pref, $l, $r){ return $pref[$r] - $pref[$l];}// Driver Code$s = "ggggggg";$n = strlen($s);$pref = array_fill(0, $n, NULL);preCompute($n, $s, $pref);// Query 1$l = 1;$r = 2;echo query($pref, $l, $r) . "\n";// Query 2$l = 1;$r = 5;echo query($pref, $l, $r) . "\n";// This code is contributed by ita_c?> |
Javascript
<script>// Javascript program to find substring with // Function to create prefix array function preCompute(n,s,pref) { pref[0] = 0; for (let i = 1; i < n; i++) { pref[i] = pref[i - 1]; if (s[i - 1]== s[i]) pref[i]++; } } // Function to return the result of the query function query(pref,l,r) { return pref[r] - pref[l]; } // Driver Code let s = "ggggggg"; let n = s.length; let pref = new Array(n); preCompute(n, s, pref); // Query 1 let l = 1; let r = 2; document.write( query(pref, l, r)+"<br>"); // Query 2 l = 1; r = 5; document.write(query(pref, l, r)+"<br>");// This code is contributed by rag2127</script> |
Output
1 4
Complexity Analysis:
- Time Complexity: O(n+k) where n is the size of the string and k is the number of queries.
- 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!
