Open In App

Count substrings consisting of equal number of a, b, c and d

Last Updated : 21 Dec, 2022
Comments
Improve
Suggest changes
Like Article
Like
Report

Given a string str, the task is to count non-empty substrings with equal number of ‘a’, ‘b’, ‘c’, and ‘d’.

Examples:

Input: str = “abcdef” 
Output: 6 
Explanation: 
Substring consisting of equal number of ‘a’, ‘b’, ‘c’, and ‘d’ are { “abcd”, “abcde”, “abcdf”, “abcdef”, “e”, “f” }. 
Therefore, the required output is 6.

Input: str = “abddcdc” 
Output: 0

Approach: The problem can be solved using Hashing. The idea is to based on the following observations:

If the frequency of the characters { 'a', 'b', 'c', 'd' } in the substring {str[0], ..., str[i] } is { p, q, r, s} and in the substring {str[0], ..., str[j] } is { p + x, q + x, r + x, s + x }, then the substring { str[i], ..., str[j] } must contain equal number of ‘a’, ‘b’, ‘c’, and ‘d’.

Follow the steps below to solve the problem: 
 

  • Initialize a variable, say cntSub, to store the count of substrings with equal number of ‘a’, ‘b’, ‘c’, ‘d’.
  • Initialize a Map, say mp, to store the relative frequency of the characters { ‘a’, ‘b’, ‘c’, ‘d’ }. 
     

If the frequency of the characters ‘a’, ‘b’, ‘c’, and ‘d’ are { p, q, r, s }, then the relative frequency of the characters are { p - y, q - y, r - y, s - y }, where y = min({p, q, r, s}) 
 


  •  
  • Iterate over the characters of the string and store the relative frequency of the characters ‘a’, ‘b’, ‘c’, and ‘d’.
  • Traverse the map using key value of the map as i, and for every key value, increment the value of cntSub by {mp[i] \choose 2}        .
  • Finally, print the value of cntSub.


 

Below is the implementation of the above approach:


 

C++ 
// C++ program to implement
// the above approach

#include <bits/stdc++.h>
using namespace std;

// Function to count the substring with
// equal number of a, b, c and d
int countSubstrings(string str)
{

    // Stores relative frequency of
    // the characters {'a', 'b', 'c', 'd'}
    map<pair<pair<int, int>,
             pair<int, int> >,
        int>
        mp;

    // Initially, frequencies of
    // 'a', 'b', 'c' and 'd' are 0.
    mp[{ { 0, 0 }, { 0, 0 } }]++;

    // Stores relative
    // frequency of 'a'
    int p = 0;

    // Stores relative
    // frequency of 'b'
    int q = 0;

    // Stores relative
    // frequency of 'c'
    int r = 0;

    // Stores relative
    // frequency of 'd'
    int s = 0;

    // Stores count of substring with equal
    // number of 'a', 'b', 'c' and 'd'
    int cntSub = 0;

    // Iterate over the characters
    // of the string
    for (int i = 0; i < str.length(); i++) {

        // If current character
        // is 'a'
        if (str[i] == 'a') {

            // Update p
            p++;

            // Stores minimum
            // of { p, q, r, s}
            int Y = min(min(s, r),
                        min(p, q));

            // Update p
            p -= Y;

            // Update q
            q -= Y;

            // Update r
            r -= Y;

            // Update s
            s -= Y;
        }

        // If current character is b
        else if (str[i] == 'b') {

            // Update q
            q++;

            // Stores minimum
            // of { p, q, r, s}
            int Y = min(min(p, q),
                        min(r, s));

            // Update p
            p -= Y;

            // Update q
            q -= Y;

            // Update r
            r -= Y;

            // Update s
            s -= Y;
        }
        else if (str[i] == 'c') {

            // Update r
            r++;

            // Stores minimum
            // of { p, q, r, s}
            int Y = min(min(p, q),
                        min(r, s));

            // Update p
            p -= Y;

            // Update q
            q -= Y;

            // Update r
            r -= Y;

            // Update s
            s -= Y;
        }
        else if (str[i] == 'd') {

            // Update s
            s++;

            // Stores minimum
            // of { p, q, r, s}
            int Y = min(min(p, q),
                        min(r, s));

            // Update p
            p -= Y;

            // Update q
            q -= Y;

            // Update r
            r -= Y;

            // Update s
            s -= Y;
        }

        // Update relative frequency
        // of {p, q, r, s}
        mp[{ { p, q }, { r, s } }]++;
    }

    // Traverse the map
    for (auto& e : mp) {

        // Stores count of
        // relative frequency
        int freq = e.second;

        // Update cntSub
        cntSub += (freq) * (freq - 1) / 2;
    }
    return cntSub;
}

// Driver Code
int main()
{

    string str = "abcdefg";

    // Function Call
    cout << countSubstrings(str);
    return 0;
}
Java 
// Java program to implement
// the above approach
import java.util.*;

class GFG
{
  
  // Function to count the substring with
  // equal number of a, b, c and d
  static int countSubstrings(String Str) 
  { 
    
    // Stores relative frequency of
    // the characters {'a', 'b', 'c', 'd'}
    var mp = new HashMap<String, Integer>();

    // Initially, frequencies of
    // 'a', 'b', 'c' and 'd' are 0.
    if (mp.containsKey("0#0#0#0"))
      mp.put("0#0#0#0", mp.get("0#0#0#0") + 1);
    else 
      mp.put("0#0#0#0", 1);

    // Stores relative
    // frequency of 'a'
    var p = 0;

    // Stores relative
    // frequency of 'b'
    var q = 0;

    // Stores relative
    // frequency of 'c'
    var r = 0;

    // Stores relative
    // frequency of 'd'
    var s = 0;

    // Stores count of substring with equal
    // number of 'a', 'b', 'c' and 'd'
    var cntSub = 0;

    // Iterate over the characters
    // of the string
    for (var i = 0; i < Str.length(); i++)
    {

      // If current character
      // is 'a'
      if (Str.charAt(i) == 'a') 
      {
        // Update p
        p += 1;

        // Stores minimum
        // of { p, q, r, s}
        var Y = Math.min(Math.min(s, r), Math.min(p, q));

        // Update p
        p -= Y;

        // Update q
        q -= Y;

        // Update r
        r -= Y;

        // Update s
        s -= Y;
      }

      // If current character is b
      else if (Str.charAt(i) == 'b') 
      {
        // Update q
        q += 1;

        // Stores minimum
        // of { p, q, r, s}
        var Y = Math.min(Math.min(p, q), Math.min(r, s));

        // Update p
        p -= Y;

        // Update q
        q -= Y;

        // Update r
        r -= Y;

        // Update s
        s -= Y;
      }  
      else if (Str.charAt(i) == 'c') 
      {
        // Update r
        r += 1;

        // Stores minimum
        // of { p, q, r, s}
        var Y = Math.min(Math.min(p, q),Math.min(r, s));

        // Update p
        p -= Y;

        // Update q
        q -= Y;

        // Update r
        r -= Y;

        // Update s
        s -= Y;
      }
      else if (Str.charAt(i) == 'd') 
      {   
        // Update s
        s += 1;

        // Stores minimum
        // of { p, q, r, s}
        var Y = Math.min(Math.min(p, q),Math.min(r, s));

        // Update p
        p -= Y;

        // Update q
        q -= Y;

        // Update r
        r -= Y;

        // Update s
        s -= Y;
      }  
      // Update relative frequency
      // of {p, q, r, s}

      String key = String.valueOf(p) + "#" + String.valueOf(q) +  "#" + String.valueOf(r) +  "#" + String.valueOf(s);
      if (mp.containsKey(key))
        mp.put(key, mp.get(key) + 1);
      else 
        mp.put(key, 1);

    }
    // Traverse the map
    for (var e : mp.entrySet())
    {
      // Stores count of
      // relative frequency
      var freq = e.getValue();

      // Update cntSub
      cntSub += Math.floor((freq) * (freq - 1) / 2);
    }
    return cntSub;
  }

  // Driver code
  public static void main(String[] args)
  {
    var Str = "abcdefg";

    // Function Call
    System.out.println(countSubstrings(Str));
  }
}

// This code is contributed by phasing17
Python3 
# Python3 program to implement
# the above approach

# Function to count the substring with
# equal number of a, b, c and d
def countSubstrings(Str) :
    
    # Stores relative frequency of
    # the characters {'a', 'b', 'c', 'd'}
    mp = {}
    
    # Initially, frequencies of
    # 'a', 'b', 'c' and 'd' are 0.
    if ((0, 0), (0, 0)) in mp :
        mp[(0, 0), (0, 0)] += 1
    else :
        mp[(0, 0), (0, 0)] = 1
        
    # Stores relative
    # frequency of 'a'
    p = 0
    
    # Stores relative
    # frequency of 'b'
    q = 0
    
    # Stores relative
    # frequency of 'c'
    r = 0
    
    # Stores relative
    # frequency of 'd'
    s = 0
    
    # Stores count of substring with equal
    # number of 'a', 'b', 'c' and 'd'
    cntSub = 0
    
    # Iterate over the characters
    # of the string
    for i in range(len(Str)) :
        
        # If current character
        # is 'a'
        if (Str[i] == 'a') :
            # Update p
            p += 1
            
            # Stores minimum
            # of { p, q, r, s}
            Y = min(min(s, r), min(p, q))
            
            # Update p
            p -= Y
            
            # Update q
            q -= Y
            
            # Update r
            r -= Y
            
            # Update s
            s -= Y
            
        # If current character is b
        elif (Str[i] == 'b') :
            
            # Update q
            q += 1
            
            # Stores minimum
            # of { p, q, r, s}
            Y = min(min(p, q), min(r, s))
            
            # Update p
            p -= Y
            
            # Update q
            q -= Y
            
            # Update r
            r -= Y
            
            # Update s
            s -= Y
            
        elif (Str[i] == 'c') :
            
            # Update r
            r += 1
            
            # Stores minimum
            # of { p, q, r, s}
            Y = min(min(p, q),min(r, s))
            
            # Update p
            p -= Y
            
            # Update q
            q -= Y
            
            # Update r
            r -= Y
            
            # Update s
            s -= Y
            
        elif (Str[i] == 'd') :
            
            # Update s
            s += 1
            
            # Stores minimum
            # of { p, q, r, s}
            Y = min(min(p, q),min(r, s))
            
            # Update p
            p -= Y
            
            # Update q
            q -= Y
            
            # Update r
            r -= Y
            
            # Update s
            s -= Y
            
        # Update relative frequency
        # of {p, q, r, s}
        if ((p, q), (r, s)) in mp :
            mp[(p, q), (r, s)] += 1
        else :
            mp[(p, q), (r, s)] = 1
            
    # Traverse the map
    for e in mp :
        
        # Stores count of
        # relative frequency
        
        freq = mp[e]
        
        # Update cntSub
        cntSub += (freq) * (freq - 1) // 2
        
    return cntSub

  # Driver code
Str = "abcdefg"

# Function Call
print(countSubstrings(Str))

# This code is contributed by divyeshrabadiya07
C# 
// C# program to implement 
// the above approach 
using System;
using System.Collections.Generic;  
class GFG {
    
    // Function to count the substring with 
    // equal number of a, b, c and d 
    static int countSubstrings(string str) 
    { 
      
        // Stores relative frequency of 
        // the characters {'a', 'b', 'c', 'd'} 
        Dictionary<Tuple<Tuple<int, int>, 
      Tuple<int, int>>, int> mp = 
        new Dictionary<Tuple<Tuple<int, int>,
      Tuple<int, int>>, int>();  
      
        // Initially, frequencies of 
        // 'a', 'b', 'c' and 'd' are 0. 
        if(mp.ContainsKey(new Tuple<Tuple<int, int>, 
                          Tuple<int, int>>(new Tuple<int, int>(0, 0), 
                                           new Tuple<int, int>(0, 0))))
        {
            mp[new Tuple<Tuple<int, int>,
               Tuple<int, int>>(new Tuple<int, int>(0, 0), 
                                new Tuple<int, int>(0, 0))]++;
        }
        else{
            mp[new Tuple<Tuple<int, int>, 
               Tuple<int, int>>(new Tuple<int, int>(0, 0),
                                new Tuple<int, int>(0, 0))] = 1;
        }
      
        // Stores relative 
        // frequency of 'a' 
        int p = 0; 
      
        // Stores relative 
        // frequency of 'b' 
        int q = 0; 
      
        // Stores relative 
        // frequency of 'c' 
        int r = 0; 
      
        // Stores relative 
        // frequency of 'd' 
        int s = 0; 
      
        // Stores count of substring with equal 
        // number of 'a', 'b', 'c' and 'd' 
        int cntSub = 0; 
      
        // Iterate over the characters 
        // of the string 
        for (int i = 0; i < str.Length; i++) { 
      
            // If current character 
            // is 'a' 
            if (str[i] == 'a') { 
      
                // Update p 
                p++; 
      
                // Stores minimum 
                // of { p, q, r, s} 
                int Y = Math.Min(Math.Min(s, r), 
                            Math.Min(p, q)); 
      
                // Update p 
                p -= Y; 
      
                // Update q 
                q -= Y; 
      
                // Update r 
                r -= Y; 
      
                // Update s 
                s -= Y; 
            } 
      
            // If current character is b 
            else if (str[i] == 'b') { 
      
                // Update q 
                q++; 
      
                // Stores minimum 
                // of { p, q, r, s} 
                int Y = Math.Min(Math.Min(p, q), 
                            Math.Min(r, s)); 
      
                // Update p 
                p -= Y; 
      
                // Update q 
                q -= Y; 
      
                // Update r 
                r -= Y; 
      
                // Update s 
                s -= Y; 
            } 
            else if (str[i] == 'c') { 
      
                // Update r 
                r++; 
      
                // Stores minimum 
                // of { p, q, r, s} 
                int Y = Math.Min(Math.Min(p, q), 
                            Math.Min(r, s)); 
      
                // Update p 
                p -= Y; 
      
                // Update q 
                q -= Y; 
      
                // Update r 
                r -= Y; 
      
                // Update s 
                s -= Y; 
            } 
            else if (str[i] == 'd') { 
      
                // Update s 
                s++; 
      
                // Stores minimum 
                // of { p, q, r, s} 
                int Y = Math.Min(Math.Min(p, q), 
                            Math.Min(r, s)); 
      
                // Update p 
                p -= Y; 
      
                // Update q 
                q -= Y; 
      
                // Update r 
                r -= Y; 
      
                // Update s 
                s -= Y; 
            } 
      
            // Update relative frequency 
            // of {p, q, r, s} 
            if(mp.ContainsKey(new Tuple<Tuple<int, int>, 
                              Tuple<int, int>>(new Tuple<int, int>(p, q), 
                                               new Tuple<int, int>(r, s))))
            {
                mp[new Tuple<Tuple<int, int>, 
                   Tuple<int, int>>(new Tuple<int, int>(p, q),
                                    new Tuple<int, int>(r, s))]++;
            }
            else{
                mp[new Tuple<Tuple<int, int>, 
                   Tuple<int, int>>(new Tuple<int, int>(p, q),
                                    new Tuple<int, int>(r, s))] = 1;
            } 
        } 
      
        // Traverse the map
        foreach(KeyValuePair<Tuple<Tuple<int, int>, 
                Tuple<int, int>>, int> e in mp) 
        { 
      
            // Stores count of 
            // relative frequency 
            int freq = e.Value; 
      
            // Update cntSub 
            cntSub += (freq) * (freq - 1) / 2; 
        } 
        return cntSub; 
    } 

  // Driver code
  static void Main()
  {
      
    string str = "abcdefg"; 
  
    // Function Call 
    Console.WriteLine(countSubstrings(str));
  }
}

// This code is contributed by divyesh072019
JavaScript 
// JS program to implement
// the above approach

// Function to count the substring with
// equal number of a, b, c and d
function countSubstrings(Str) 
{ 
    // Stores relative frequency of
    // the characters {'a', 'b', 'c', 'd'}
    let mp = {}
    
    // Initially, frequencies of
    // 'a', 'b', 'c' and 'd' are 0.
    if (mp.hasOwnProperty('0#0#0#0'))
        mp['0#0#0#0'] += 1
    else 
        mp['0#0#0#0'] = 1
        
    // Stores relative
    // frequency of 'a'
    let p = 0
    
    // Stores relative
    // frequency of 'b'
    let q = 0
    
    // Stores relative
    // frequency of 'c'
    let r = 0
    
    // Stores relative
    // frequency of 'd'
    let s = 0
    
    // Stores count of substring with equal
    // number of 'a', 'b', 'c' and 'd'
    let cntSub = 0
    
    // Iterate over the characters
    // of the string
    for (var i = 0; i < Str.length; i++)
    {
        
        // If current character
        // is 'a'
        if (Str.charAt(i) == 'a') 
        {
            // Update p
            p += 1
            
            // Stores minimum
            // of { p, q, r, s}
            let Y = Math.min(Math.min(s, r), Math.min(p, q))
            
            // Update p
            p -= Y
            
            // Update q
            q -= Y
            
            // Update r
            r -= Y
            
            // Update s
            s -= Y
        }
        
        // If current character is b
        else if (Str[i] == 'b') 
        {
            // Update q
            q += 1
            
            // Stores minimum
            // of { p, q, r, s}
            let Y = Math.min(Math.min(p, q), Math.min(r, s))
            
            // Update p
            p -= Y
            
            // Update q
            q -= Y
            
            // Update r
            r -= Y
            
            // Update s
            s -= Y
        }  
        else if (Str[i] == 'c') 
        {
            // Update r
            r += 1
            
            // Stores minimum
            // of { p, q, r, s}
            let Y = Math.min(Math.min(p, q),Math.min(r, s))
            
            // Update p
            p -= Y
            
            // Update q
            q -= Y
            
            // Update r
            r -= Y
            
            // Update s
            s -= Y
        }
        else if (Str[i] == 'd') 
        {   
            // Update s
            s += 1
            
            // Stores minimum
            // of { p, q, r, s}
            Y = Math.min(Math.min(p, q),Math.min(r, s))
            
            // Update p
            p -= Y
            
            // Update q
            q -= Y
            
            // Update r
            r -= Y
            
            // Update s
            s -= Y
        }  
        // Update relative frequency
        // of {p, q, r, s}
        
        let key = `${p}#${q}#${r}#${s}` 
        if (mp.hasOwnProperty(key))
            mp[key] += 1
        else 
            mp[key] = 1
    
    }
    // Traverse the map
    for (let e of Object.keys(mp)) 
    {
        // Stores count of
        // relative frequency
        
        freq = mp[e]
        
        // Update cntSub
        cntSub += Math.floor((freq) * (freq - 1) / 2)
    }
    return cntSub
}

// Driver code
let Str = "abcdefg"

// Function Call
console.log(countSubstrings(Str))

// This code is contributed by phasing17

 
 


Output: 
10

 


 

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


 


Next Article
Count number of substrings of a string consisting of same characters
author
shahbazalam75508
Improve
Article Tags :
Practice Tags :

Similar Reads

We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox
  翻译：