Cuente las substrings que consisten en el mismo número de a, b, c y d

Dada una string str , la tarea es contar substrings no vacías con el mismo número de ‘a’ , ‘b’ , ‘c’ y ‘d’ .

Ejemplos:

Entrada: str = «abcdef» 
Salida: 6 
Explicación: 
Substring que consiste en el mismo número de ‘a’ , ‘b’ , ‘c’ y ‘d’ son { «abcd», «abcde», «abcdf», «abcdef ”, “e”, “f” }. 
Por lo tanto, la salida requerida es 6.

Entrada: str = “abddcdc” 
Salida: 0

Enfoque: El problema se puede resolver usando Hashing . La idea es basarse en las siguientes observaciones:

Si la frecuencia de los caracteres { ‘a’, ‘b’, ‘c’, ‘d’ } en la substring {str[0], …, str[i] } es { p, q, r, s} y en la substring {str[0], …, str[j] } es { p + x, q + x, r + x, s + x }, entonces la substring { str[i], …, str[j] } debe contener el mismo número de ‘a’ , ‘b’ , ‘c’ y ‘d’ .

Siga los pasos a continuación para resolver el problema: 
 

• Inicialice una variable, digamos cntSub , para almacenar el recuento de substrings con el mismo número de ‘a’ , ‘b’ , ‘c’ , ‘d’ .
• Inicialice un mapa , digamos mp , para almacenar la frecuencia relativa de los caracteres { ‘a’ , ‘b’ , ‘c’ , ‘d’ }. 
   

Si la frecuencia de los caracteres ‘a’ , ‘b’ , ‘c’ y ‘d’ son { p, q, r, s }, entonces la frecuencia relativa de los caracteres es { p – y, q – y, r – y, s – y }, donde y = min({p, q, r, s}) 
 

•  
• Iterar sobre los caracteres de la string y almacenar la frecuencia relativa de los caracteres ‘a’ , ‘b’ , ‘c’ y ‘d’ .
• Recorra el mapa usando el valor clave del mapa como i , y para cada valor clave, incremente el valor de cntSub en  .
• Finalmente, imprima el valor de cntSub .

A continuación se muestra la implementación del enfoque anterior:

// 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;
}

# 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# 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

10

Complejidad de tiempo: O(N * Log(N))  
Espacio auxiliar: O(N)