Substring de longitud K que tiene la frecuencia máxima en la string dada

Dada una string str , la tarea es encontrar la substring de longitud K que ocurre la mayor cantidad de veces. Si aparece más de una string el número máximo de veces, imprima la substring lexicográficamente más pequeña.

Ejemplos:

Entrada: str = “bbbbbaaaaabbabababa”, K = 5
Salida: ababa
Explicación:
Las substrings de longitud 5 de las strings anteriores son {bbbbb, bbbba, bbbaa, bbaaa, baaaa, aaaaa, aaaab, aaabb, aabba, abbab, bbaba, babab , ababa, babab, ababa}.
Entre todas ellas, las substrings {ababa, babab} aparecen el máximo número de veces (= 2).
La string lexicográficamente más pequeña de {ababa, babab} es ababa.
Por lo tanto, «ababa» es la respuesta requerida.

Entrada:  str = “heisagoodboy”, K = 5
Salida: agood
Explicación: 
Las substrings de longitud 5 de la string anterior son {heisa, eisag, isago, sagoo, agood, goodb, oodbo, odboy}.
Todos ellos ocurren una sola vez. Pero la string lexicográficamente más pequeña entre ellos es «agood».
Por lo tanto, «un bien» es la respuesta requerida.

Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todas las substrings de tamaño K a partir de la string dada y almacenar la frecuencia de cada substring en un Map . Luego, recorra el Mapa y encuentre la substring lexicográficamente más pequeña que ocurra el máximo número de veces e imprímala. 
Complejidad de tiempo: O(N*( K + log K))
Espacio auxiliar: O(N * K)

Enfoque Eficiente: Para optimizar el enfoque anterior, la idea es utilizar la técnica de Ventana Deslizante . Considere una ventana de tamaño 
K para generar todas las substrings de longitud K y cuente la frecuencia de una substring generada en un Map . Recorre el mapa y encuentra la substring que ocurre el máximo número de veces e imprímela. Si existen varios de ellos, imprima la substring lexicográficamente más pequeña.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using ll = long long int;
using namespace std;
 
// Function that generates substring
// of length K that occurs maximum times
void maximumOccurringString(string s, ll K)
{
    // Store the frequency of substrings
    map<deque<char>, ll> M;
 
    ll i;
 
    // Deque to maintain substrings
    // window size K
    deque<char> D;
 
    for (i = 0; i < K; i++) {
        D.push_back(s[i]);
    }
 
    // Update the frequency of the
    // first substring in the Map
    M[D]++;
 
    // Remove the first character of
    // the previous K length substring
    D.pop_front();
 
    // Traverse the string
    for (ll j = i; j < s.size(); j++) {
 
        // Insert the current character
        // as last character of
        // current substring
        D.push_back(s[j]);
 
        M[D]++;
 
        // Pop the first character of
        // previous K length substring
        D.pop_front();
    }
 
    ll maxi = INT_MIN;
 
    deque<char> ans;
 
    // Find the substring that occurs
    // maximum number of times
    for (auto it : M) {
        if (it.second > maxi) {
            maxi = it.second;
            ans = it.first;
        }
    }
 
    // Print the substring
    for (ll i = 0; i < ans.size(); i++) {
        cout << ans[i];
    }
}
 
// Driver Code
int main()
{
    // Given string
    string s = "bbbbbaaaaabbabababa";
 
    // Given K size of substring
    ll K = 5;
 
    // Function Call
    maximumOccurringString(s, K);
 
    return 0;
}

# Python3 program for the above approach
from collections import deque, Counter, defaultdict
import sys
 
# Function that generates substring
# of length K that occurs maximum times
def maximumOccurringString(s, K):
     
    # Store the frequency of substrings
    M = {}
 
    # Deque to maintain substrings
    # window size K
    D = deque()
 
    for i in range(K):
        D.append(s[i])
 
    # Update the frequency of the
    # first substring in the Map
    # E="".join(list(D
    M[str("".join(list(D)))] = M.get(
        str("".join(list(D))), 0) + 1
 
    # Remove the first character of
    # the previous K length substring
    D.popleft()
 
    # Traverse the string
    for j in range(i, len(s)):
 
        # Insert the current character
        # as last character of
        # current substring
        D.append(s[j])
 
        M[str("".join(list(D)))] = M.get(
            str("".join(list(D))), 0) + 1
 
        # Pop the first character of
        # previous K length substring
        D.popleft()
 
    maxi = -sys.maxsize - 1
 
    ans = deque()
 
    # Find the substring that occurs
    # maximum number of times
    # print(M)
    for it in M:
         
        # print(it[0])
        if (M[it] >= maxi):
            maxi = M[it]
             
            # print(maxi)
            ans = it
 
    # Print the substring
    for i in range(len(ans)):
        print(ans[i], end = "")
 
# Driver Code
if __name__ == '__main__':
     
    # Given string
    s = "bbbbbaaaaabbabababa"
 
    # Given K size of substring
    K = 5
 
    # Function call
    maximumOccurringString(s, K)
 
# This code is contributed by mohit kumar 29

ababa

Complejidad de tiempo: O((N – K)*log(N – K))
Espacio auxiliar: O(N – K)