Horje
Count odd length Substrings with median same as Kth character of String

Given a string S of size N, the task is to find the number of substrings of odd lengths that have a median equal to the Kth character of the string.

Examples:

Input: S = “ecadgg”, K = 4
Output: 4
Explanation: Character at 4th position in string is ‘d’. 
Then there are 4 odd length substrings with ‘d’ as their median: 
[d], [a, d, g], [e, c, a, d, g], therefore return 4 as the answer.

Input: s = “abc”, K = 1
Output: 1
Explanation: Character at 1st position in string is ‘a’. Then there is only 1 odd length substring with ‘a’ as its median: [a] therefore return 1 as the answer.

Approach: To solve the problem follow the below idea:

Median is middle element. So smaller elements has to be equal to number of bigger elements, the desired substrings would be like (S[K]) or (2 elements on left and right), (4 elements on left and right), so on. . . [cannot take 1, 3 . . . because the substring should have odd length]

  • We can maintain smaller and bigger arrays of length N and populate them.
  • This helps us to find in range [i, j] count of smaller and bigger elements with respect to S[K]. 
    • For S[K] to be median in the range [i, j], the number of characters smaller than S[K] should be equal to the number of characters greater than S[K] and the subarray should include S[K].

Note: We are considering 1based indexing of string for understanding but the actual implementation uses 0 based indexing.

Follow the steps to solve the problem:

  • Create two vectors namely greater and smaller of size N.
  • Traverse the string: 
    • Mark 1 in a smaller vector at ith position, if the character at that index is smaller than the Kth character of the string, and 
    • Mark 1 in a greater vector at the ith position if the character is greater than the Kth character of the string.
  • Create a difference array that stores the difference of smaller and greater for each ith position.
  • Use prefix sum on difference array to find valid subarrays. In valid subarrays, the sum will be 0.
    • Use the prefix sum for the following three segments:
      • start = 0 and end = N and store it in val1,  
      • start = 0 and end = K-1 store it in val2 and 
      • start = K and end = N and store it in val3.
  • In the end, return val1 – val2 – val3, which is the count of substrings with equally smaller and greater elements that contain Kth character.

Below is the implementation of the above approach.

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function for finding the number of
// sub strings in (start, end) where
// sum of difference is zero
int sum(int start, int end, vector<int>& v)
{
    // STL map to store number of subarrays
    // starting from index zero having
    // particular value of sum.
    unordered_map<int, int> prevSum;
 
    int res = 0, currSum = 0;
 
    for (int i = start; i < end; i++) {
 
        // Add current element to sum so far.
        currSum += v[i];
 
        // If currsum is equal to 0, then
        // a new subarray is found.
        // So increase count of subarrays.
        if (currSum == 0)
            res++;
 
        if (prevSum.find(currSum) != prevSum.end())
            res += (prevSum[currSum]);
 
        // Add currsum value to count of
        // different values of sum.
        prevSum[currSum]++;
    }
 
    return res;
}
 
// Function to find odd length substrings
// whose median is equal to s[k-1]
int numberOfSubstrings(string& s, int k)
{
    int n = s.size();
 
    // Initializing vectors for storing
    // element is smaller or greater
    // than median
    vector<int> smaller(n, 0), greater(n, 0);
    for (int i = 0; i < n; i++) {
        smaller[i] = s[i] < s[k - 1];
 
        greater[i] = s[i] > s[k - 1];
    }
 
    // Declaring a vector to store
    // difference of greater and smaller
    // characters for each position
    vector<int> diff(n, 0);
    for (int i = 0; i < n; i++)
        diff[i] = smaller[i] - greater[i];
 
    // Substrings in (0 to n)
    int val1 = sum(0, n, diff);
 
    // Substrings  in (0 to k-1)
    int val2 = sum(0, k - 1, diff);
 
    // Substrings in (k to n)
    int val3 = sum(k, n, diff);
 
    // Considering only those sub strings
    // with difference 0 that
    // contains s[k-1]
    return val1 - val2 - val3;
}
 
// Driver code
int main()
{
    string S = "ecadgg";
    int K = 4;
 
    // Function call
    cout << numberOfSubstrings(S, K);
 
    return 0;
}

Java

// Java code to implement the approach
import java.io.*;
import java.util.*;
 
class GFG {
    // Function for finding the number of
    // sub strings in (start, end) where
    // sum of difference is zero
    public static int sum(int start, int end, int v[])
    {
        // STL map to store number of subarrays
        // starting from index zero having
        // particular value of sum.
        HashMap<Integer, Integer> prevSum
            = new HashMap<Integer, Integer>();
 
        int res = 0, currSum = 0;
 
        for (int i = start; i < end; i++) {
 
            // Add current element to sum so far.
            currSum += v[i];
 
            // If currsum is equal to 0, then
            // a new subarray is found.
            // So increase count of subarrays.
            if (currSum == 0)
                res++;
 
            if (prevSum.containsKey(currSum)) {
                res += prevSum.get(currSum);
                prevSum.put(currSum,
                            prevSum.get(currSum) + 1);
            }
            // Add currsum value to count of
            // different values of sum.
            prevSum.put(currSum, 1);
        }
 
        return res;
    }
 
    // Function to find odd length substrings
    // whose median is equal to s[k-1]
    public static int numberOfSubstrings(String s, int k)
    {
        int n = s.length();
 
        // Initializing vectors for storing
        // element is smaller or greater
        // than median
        int smaller[] = new int[n];
        int greater[] = new int[n];
        for (int i = 0; i < n; i++) {
            smaller[i]
                = (s.charAt(i) < s.charAt(k - 1)) ? 1 : 0;
 
            greater[i]
                = (s.charAt(i) > s.charAt(k - 1)) ? 1 : 0;
        }
 
        // Declaring a vector to store
        // difference of greater and smaller
        // characters for each position
        int diff[] = new int[n];
        for (int i = 0; i < n; i++)
            diff[i] = smaller[i] - greater[i];
 
        // Substrings in (0 to n)
        int val1 = sum(0, n, diff);
 
        // Substrings  in (0 to k-1)
        int val2 = sum(0, k - 1, diff);
 
        // Substrings in (k to n)
        int val3 = sum(k, n, diff);
 
        // Considering only those sub strings
        // with difference 0 that
        // contains s[k-1]
        return val1 - val2 - val3;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        String S = "ecadgg";
        int K = 4;
 
        // Function call
        System.out.print(numberOfSubstrings(S, K));
    }
}
 
// This code is contributed by Rohit Pradhan

Python3

# Python code for the above approach
 
# Function for finding the number of
# sub strings in (start, end) where
# sum of difference is zero
def sum(start, end, v):
   
    # STL map to store number of subarrays
    # starting from index zero having
    # particular value of sum.
    prevSum = {};
 
    res = 0
    currSum = 0;
 
    for i in range(start, end):
 
        # Add current element to sum so far.
        currSum += v[i];
 
        # If currsum is equal to 0, then
        # a new subarray is found.
        # So increase count of subarrays.
        if (currSum == 0):
            res += 1
 
        if (currSum in prevSum):
            res += (prevSum[currSum]);
 
 
        # Add currsum value to count of
        # different values of sum.
        if (currSum in prevSum):
            prevSum[currSum] += 1
        else:
            prevSum[currSum] = 1
    return res;
 
# Function to find odd length substrings
# whose median is equal to s[k-1]
def numberOfSubstrings(s, k):
    n = len(s)
 
    # Initializing vectors for storing
    # element is smaller or greater
    # than median
    smaller = [0] * n
    greater = [0] * n
    for i in range(n):
        smaller[i] = s[i] < s[k - 1];
 
        greater[i] = s[i] > s[k - 1];
     
 
    # Declaring a vector to store
    # difference of greater and smaller
    # characters for each position
    diff = [0] * n
    for i in range(n):
        diff[i] = smaller[i] - greater[i];
 
    # Substrings in (0 to n)
    val1 = sum(0, n, diff);
 
    # Substrings  in (0 to k-1)
    val2 = sum(0, k - 1, diff);
 
    # Substrings in (k to n)
    val3 = sum(k, n, diff);
 
    # Considering only those sub strings
    # with difference 0 that
    # contains s[k-1]
    return val1 - val2 - val3;
 
# Driver code
S = "ecadgg";
K = 4;
 
# Function call
print(numberOfSubstrings(S, K));
 
 # This code is contributed by Saurabh Jaiswal
 
    

C#

// C# code for the above approach
 
using System;
using System.Collections;
using System.Collections.Generic;
 
public class GFG {
 
    // Function for finding the number of
    // sub strings in (start, end) where
    // sum of difference is zero
    public static int sum(int start, int end, int[] v)
    {
        // Dictionary to store number of subarrays
        // starting from index zero having
        // particular value of sum.
        Dictionary<int, int> prevSum
            = new Dictionary<int, int>();
 
        int res = 0, currSum = 0;
 
        for (int i = start; i < end; i++) {
 
            // Add current element to sum so far.
            currSum += v[i];
 
            // If currsum is equal to 0, then
            // a new subarray is found.
            // So increase count of subarrays.
            if (currSum == 0)
                res++;
 
            if (prevSum.ContainsKey(currSum)) {
                res += prevSum[currSum];
                prevSum[currSum] += 1;
            }
            // Add currsum value to count of
            // different values of sum.
            else {
                prevSum.Add(currSum, 1);
            }
        }
 
        return res;
    }
 
    // Function to find odd length substrings
    // whose median is equal to s[k-1]
    public static int numberOfSubstrings(String s, int k)
    {
        int n = s.Length;
 
        // Initializing vectors for storing
        // element is smaller or greater
        // than median
        int[] smaller = new int[n];
        int[] greater = new int[n];
        for (int i = 0; i < n; i++) {
            smaller[i] = (s[i] < s[k - 1]) ? 1 : 0;
            greater[i] = (s[i] > s[k - 1]) ? 1 : 0;
        }
 
        // Declaring a vector to store
        // difference of greater and smaller
        // characters for each position
        int[] diff = new int[n];
        for (int i = 0; i < n; i++)
            diff[i] = smaller[i] - greater[i];
 
        // Substrings in (0 to n)
        int val1 = sum(0, n, diff);
 
        // Substrings  in (0 to k-1)
        int val2 = sum(0, k - 1, diff);
 
        // Substrings in (k to n)
        int val3 = sum(k, n, diff);
 
        // Considering only those sub strings
        // with difference 0 that
        // contains s[k-1]
        return val1 - val2 - val3;
    }
 
    static public void Main()
    {
 
        // Code
        String S = "ecadgg";
        int K = 4;
 
        // Function call
        Console.Write(numberOfSubstrings(S, K));
    }
}
 
// This code is contributed by lokeshmvs21.

Javascript

   <script>
       // JavaScript code for the above approach
 
       // Function for finding the number of
       // sub strings in (start, end) where
       // sum of difference is zero
 
       function sum(start, end, v) {
           // STL map to store number of subarrays
           // starting from index zero having
           // particular value of sum.
           let prevSum = new Map();
 
           let res = 0, currSum = 0;
 
           for (let i = start; i < end; i++) {
 
               // Add current element to sum so far.
               currSum += v[i];
 
               // If currsum is equal to 0, then
               // a new subarray is found.
               // So increase count of subarrays.
               if (currSum == 0)
                   res++;
 
               if (prevSum.has(currSum))
                   res += (prevSum.get(currSum));
 
 
               // Add currsum value to count of
               // different values of sum.
 
               if (prevSum.has(currSum))
                   prevSum.set(currSum, prevSum.get(currSum) + 1);
               else
                   prevSum.set(currSum, 1);
           }
 
           return res;
       }
 
       // Function to find odd length substrings
       // whose median is equal to s[k-1]
       function numberOfSubstrings(s, k) {
           let n = s.length;
 
           // Initializing vectors for storing
           // element is smaller or greater
           // than median
           let smaller = new Array(n).fill(0), greater = new Array(n).fill(0);
           for (let i = 0; i < n; i++) {
               smaller[i] = s[i] < s[k - 1];
 
               greater[i] = s[i] > s[k - 1];
           }
 
           // Declaring a vector to store
           // difference of greater and smaller
           // characters for each position
           let diff = new Array(n).fill(0);
           for (let i = 0; i < n; i++)
               diff[i] = smaller[i] - greater[i];
 
           // Substrings in (0 to n)
           let val1 = sum(0, n, diff);
 
           // Substrings  in (0 to k-1)
           let val2 = sum(0, k - 1, diff);
 
           // Substrings in (k to n)
           let val3 = sum(k, n, diff);
 
           // Considering only those sub strings
           // with difference 0 that
           // contains s[k-1]
           return val1 - val2 - val3;
       }
 
       // Driver code
       let S = "ecadgg";
       let K = 4;
 
       // Function call
       document.write(numberOfSubstrings(S, K));
 
// This code is contributed by Potta Lokesh
 
   </script>

Output

4

Time Complexity: O(N)
Auxiliary Space: O(N)


 


Reffered: https://www.geeksforgeeks.org

Strings

Related
Print Words with Prime length from a Sentence Print Words with Prime length from a Sentence
How to insert characters in a string at a certain position? How to insert characters in a string at a certain position?
Find Strings formed by replacing prefixes of given String with given characters Find Strings formed by replacing prefixes of given String with given characters
Make all Strings palindrome by swapping characters from adjacent Strings Make all Strings palindrome by swapping characters from adjacent Strings
Count ways to split string into K Substrings starting with even digit and min length M Count ways to split string into K Substrings starting with even digit and min length M

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



 

Horje