Horje
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)


 


Reffered: https://www.geeksforgeeks.org

Arrays

Related
Find Maximum Difference Between any Two Pairs By Following Operations Optimally Find Maximum Difference Between any Two Pairs By Following Operations Optimally
Make Array Equal Make Array Equal
Increasing Decreasing Update Queries (Akku and Arrays) Increasing Decreasing Update Queries (Akku and Arrays)
Nitika and her queries Nitika and her queries
Maximum Sum of Array with given MEX Maximum Sum of Array with given MEX

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 14



 

Horje