Queries to find number of indexes where characters repeated twice in row in substring L to R
Given string S of size N consisting of lower case characters and 2d array Q[][2] of size M representing several queries of type {L, R} representing a range. The task for this problem is for each query {L, R} to find several indexes where characters are repeated twice in a row in substring L to R.
Examples:
Input: S = “mississippi”, Q[][2] = {{3, 9}, {4, 10}, {4, 6}, {7, 7}}
Output: 2 2 0 0
Explanation:
- First query {3, 9} substring is [s, s, i, s, s, i, p]. There are 2 indexes where characters are repeated twice in row. Indexes are (1, 2) and (4, 5).
- Second query {4, 10} substring is [s, i, s, s, i, p, p]. There are 2 indexes where characters are repeated twice in row. Indexes are (3, 4) and (6, 7).
- Third query {4, 6} substring is [s, i, s]. There are 0 indexes where characters are repeated twice in row.
- Fourth query {7, 7} substring is [s]. There are 0 indexes where characters are repeated twice in row.
Input: S = “aaaaa”, Q[][2] = {{1, 5}}
Output: 4
Explanation:
- First query {1, 5} substring is [a, a, a, a, a] There are four indexes where characters are repeated twice in row. Indexes are (1, 2), (2, 3), (3, 4) and (4, 5).
Efficient Approach: To solve the problem follow the below idea:
Prefix sum array is used to solve this problem.
Illustration:
- let’s say S = “assaccc” prefixSumArray[] = {0, 0, 0, 0, 0, 0}
- If S[i] and S[i – 1] are equal then mark i’th position 1 in our prefixSumArray[], and it becomes prefixSumArray[] = {0, 0, 1, 0, 0, 1, 1}
- If we take prefix sum of this array it becomes prefixSumArray[] = {0, 0, 1, 1, 1, 2, 3}
- Let say we want to find out the number of indexes where characters are repeated twice in row (that is S[i] = S[i – 1]) in substring of range L = 2 to R = 5 which is S[2:5] = “ssac” the answer will be prefixSumArray[R] – prefixSumArray[L – 1] = 1 – 0 = 1 so there is 1 index where two equal characters are consecutive.
- Special case: let say range L = 3 to R = 5 the substring is S[3:5] = “sac” in this case prefixSumArray[R] – prefixSumArray[L – 1] = 1 – 0 = 1 which says there is 1 index where characters are repeating consecutively but in string “sac” there are no such index. so this is case where L – 1’th character (which is index 2) is equal to L’th because of that we have extra one in our answer. To handle this we will subtract our answer by 1 when S[L] is equal to S[L – 1] when solving each query.
Below are the steps for the above approach:
- Declaring array prefixSum[].
- Iterating in string S if the previous character is equal to current increment prefixSum[] array at that position by 1.
- Take prefix sum by iterating over N elements.
- Iterate for M queries and for each query declare variables L and R to store Q[i][0] and Q[i][1] representing range.
- Declare another variable numberOfIndexes = prefixSum[R] – prefixSum[L – 1] to store number of indexes where characters are repeated twice in row.
- if the characters at index L – 1 and L are equal subtract 1 from numberOfIndexes because it will keep extra 1 in prefix sum which is generated because of equality of L – 1’th and L’th characters (Special case).
- print numberOfIndexes.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to answe Queries to find number of characters // repeated twice in row in substring L to R int queriesToFindLR(string S, int N, int Q[][2], int M) { // Declaring Prefix Sum array vector< int > prefixSum(N + 1, 0); // Populating Prefix array for ( int i = 1; i < N; i++) { // if last two characters are same if (S[i] == S[i - 1]) prefixSum[i + 1]++; } // taking prefix sum of this array for ( int i = 1; i <= N; i++) { prefixSum[i] = prefixSum[i] + prefixSum[i - 1]; } // iterate for M queries for ( int i = 0; i < M; i++) { // query to find answer in L to R int L = Q[i][0], R = Q[i][1]; // numberOfIndexes which has repeated characters in // row int numberOfindexes = prefixSum[R] - prefixSum[L - 1]; // if L - 1 was equal to L subtract 1 if (L - 2 >= 0 and S[L - 1] == S[L - 2]) numberOfindexes--; // answer for the query cout << numberOfindexes << " "; } // finish on next line for next test case cout << endl; } // Driver Code int32_t main() { // Input 1 int N = 11, M = 4; string S = "mississippi"; int Q[][2] = { { 3, 9 }, { 8, 10 }, { 4, 6 }, { 7, 7 } }; // Function Call queriesToFindLR(S, N, Q, M); return 0; } |
Java
import java.util.*; class Main { // Function to answer Queries to find the number of characters // repeated twice in a row in substring L to R static void queriesToFindLR(String S, int N, int [][] Q, int M) { // Declaring Prefix Sum array int [] prefixSum = new int [N + 1 ]; // Populating Prefix array for ( int i = 1 ; i < N; i++) { // if last two characters are the same if (S.charAt(i) == S.charAt(i - 1 )) prefixSum[i + 1 ]++; } // Taking the prefix sum of this array for ( int i = 1 ; i <= N; i++) { prefixSum[i] = prefixSum[i] + prefixSum[i - 1 ]; } // Iterate for M queries for ( int i = 0 ; i < M; i++) { // Query to find the answer in L to R int L = Q[i][ 0 ], R = Q[i][ 1 ]; // Number of indexes which have repeated characters in a row int numberOfIndexes = prefixSum[R] - prefixSum[L - 1 ]; // If L - 1 was equal to L, subtract 1 if (L - 2 >= 0 && S.charAt(L - 1 ) == S.charAt(L - 2 )) numberOfIndexes--; // Answer for the query System.out.print(numberOfIndexes + " " ); } // Finish on the next line for the next test case System.out.println(); } // Driver Code public static void main(String[] args) { int N = 11 , M = 4 ; String S = "mississippi" ; int [][] Q = { { 3 , 9 }, { 8 , 10 }, { 4 , 6 }, { 7 , 7 } }; // Function Call queriesToFindLR(S, N, Q, M); } } |
Python3
def queries_to_find_LR(s, n, q, m): """ Function to answer Queries to find the number of characters repeated twice in a row in the substring L to R """ # Declaring Prefix Sum array prefix_sum = [ 0 ] * (n + 1 ) # Populating Prefix array for i in range ( 1 , n): # if the last two characters are the same if s[i] = = s[i - 1 ]: prefix_sum[i + 1 ] + = 1 # taking the prefix sum of this array for i in range ( 1 , n + 1 ): prefix_sum[i] = prefix_sum[i] + prefix_sum[i - 1 ] # iterate for M queries for i in range (m): # query to find the answer in L to R L, R = q[i][ 0 ], q[i][ 1 ] # number of indexes which have repeated characters in a row number_of_indexes = prefix_sum[R] - prefix_sum[L - 1 ] # if L - 1 was equal to L, subtract 1 if L - 2 > = 0 and s[L - 1 ] = = s[L - 2 ]: number_of_indexes - = 1 # answer for the query print (number_of_indexes, end = " " ) # finish on the next line for the next test case print () # Driver Code if __name__ = = "__main__" : # Input 1 N, M = 11 , 4 S = "mississippi" Q = [[ 3 , 9 ], [ 8 , 10 ], [ 4 , 6 ], [ 7 , 7 ]] # Function Call queries_to_find_LR(S, N, Q, M) |
C#
using System; class GFG { // Function to answer queries to find number of // characters repeated twice in a row in substring L to // R static void QueriesToFindLR( string S, int N, int [, ] Q, int M) { // Declaring Prefix Sum array int [] prefixSum = new int [N + 1]; // Populating Prefix array for ( int i = 1; i < N; i++) { // if last two characters are the same if (S[i] == S[i - 1]) prefixSum[i + 1]++; } // Taking prefix sum of this array for ( int i = 1; i <= N; i++) { prefixSum[i] = prefixSum[i] + prefixSum[i - 1]; } // Iterate for M queries for ( int i = 0; i < M; i++) { // Query to find answer in L to R int L = Q[i, 0], R = Q[i, 1]; // Number of indexes which have repeated // characters in row int numberOfIndexes = prefixSum[R] - prefixSum[L - 1]; // If L - 1 was equal to L, subtract 1 if (L - 2 >= 0 && S[L - 1] == S[L - 2]) numberOfIndexes--; // Answer for the query Console.Write(numberOfIndexes + " " ); } // Finish on the next line for the next test case Console.WriteLine(); } // Driver Code static void Main() { // Input int N = 11, M = 4; string S = "mississippi" ; int [, ] Q = { { 3, 9 }, { 8, 10 }, { 4, 6 }, { 7, 7 } }; // Function Call QueriesToFindLR(S, N, Q, M); } } |
Javascript
// Javascript code // Function to answer Queries to find the number of characters // repeated twice in a row in substring L to R function queriesToFindLR(S, N, Q, M) { // Declaring Prefix Sum array let prefixSum = new Array(N + 1).fill(0); // Populating Prefix array for (let i = 1; i < N; i++) { // if last two characters are the same if (S.charAt(i) === S.charAt(i - 1)) { prefixSum[i + 1]++; } } // Taking the prefix sum of this array for (let i = 1; i <= N; i++) { prefixSum[i] = prefixSum[i] + prefixSum[i - 1]; } // Iterate for M queries for (let i = 0; i < M; i++) { // Query to find the answer in L to R let L = Q[i][0], R = Q[i][1]; // Number of indexes which have repeated characters in a row let numberOfIndexes = prefixSum[R] - prefixSum[L - 1]; // If L - 1 was equal to L, subtract 1 if (L - 2 >= 0 && S.charAt(L - 1) === S.charAt(L - 2)) { numberOfIndexes--; } // Answer for the query process.stdout.write(numberOfIndexes + " " ); } // Finish on the next line for the next test case console.log(); } // Driver Code function main() { let N = 11, M = 4; let S = "mississippi" ; let Q = [ [3, 9], [8, 10], [4, 6], [7, 7] ]; // Function Call queriesToFindLR(S, N, Q, M); } // Invoke the main function main(); |
Output
2 1 0 0
Time Complexity: O(N + Q)
Auxiliary Space: O(N)