Recuento máximo de substrings de longitud K que constan de los mismos caracteres

Dada una string str y un entero k . La tarea es contar las ocurrencias de substrings de longitud k que constan de los mismos caracteres. Puede haber varias substrings posibles de longitud k, elija el recuento de la que aparece el número máximo de veces como la substring (no superpuesta) de str .
Ejemplos: 
 

Entrada: str = “aaacaabbaa”, k = 2 
Salida: 3 
“aa” y “bb” son las únicas substrings de longitud 2 que constan de los mismos caracteres. 
“bb” aparece solo una vez como una substring de str mientras que “aa” aparece tres veces (que es la respuesta)
Entrada: str = “abab”, k = 2 
Salida: 0 
 

Enfoque: iterar sobre todos los caracteres de ‘a’ a ‘z’ y contar el número de veces que una string de longitud k que consta solo del carácter actual aparece como una substring de str . Imprime el máximo de estos recuentos al final.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count
// of the required sub-strings
int maxSubStrings(string s, int k)
{
    int maxSubStr = 0, n = s.size();
 
    // Iterate over all characters
    for (int c = 0; c < 26; c++) {
        char ch = 'a' + c;
 
        // Count with current character
        int curr = 0;
        for (int i = 0; i <= n - k; i++) {
            if (s[i] != ch)
                continue;
            int cnt = 0;
            while (i < n && s[i] == ch && cnt != k) {
                i++;
                cnt++;
            }
            i--;
 
            // If the substring has a length k
            // then increment count with current character
            if (cnt == k)
                curr++;
        }
 
        // Update max count
        maxSubStr = max(maxSubStr, curr);
    }
    return maxSubStr;
}
 
// Driver Code
int main()
{
    string s = "aaacaabbaa";
    int k = 2;
    cout << maxSubStrings(s, k);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
import java.lang.*;
import java.io.*;
 
class GFG
{
     
// Function to return the count
// of the required sub-strings
static int maxSubStrings(String s, int k)
{
    int maxSubStr = 0, n = s.length();
 
    // Iterate over all characters
    for (int c = 0; c < 26; c++)
    {
        char ch = (char)((int)'a' + c);
 
        // Count with current character
        int curr = 0;
        for (int i = 0; i <= n - k; i++)
        {
            if (s.charAt(i) != ch)
                continue;
            int cnt = 0;
            while (i < n && s.charAt(i) == ch &&
                                        cnt != k)
            {
                i++;
                cnt++;
            }
            i--;
 
            // If the substring has a length
            //  k then increment count with
            // current character
            if (cnt == k)
                curr++;
        }
 
        // Update max count
        maxSubStr = Math.max(maxSubStr, curr);
    }
    return maxSubStr;
}
 
// Driver Code
public static void main(String []args)
{
    String s = "aaacaabbaa";
    int k = 2;
    System.out.println(maxSubStrings(s, k));
}
}
 
// This code is contributed by
// tufan_gupta2000

# Python 3 implementation of the approach
 
# Function to return the count
# of the required sub-strings
def maxSubStrings(s, k):
    maxSubStr = 0
    n = len(s)
 
    # Iterate over all characters
    for c in range(27):
        ch = chr(ord('a') + c)
 
        # Count with current character
        curr = 0
        for i in range(n - k):
            if (s[i] != ch):
                continue
            cnt = 0
            while (i < n and s[i] == ch and
                                   cnt != k):
                i += 1
                cnt += 1
     
            i -= 1
 
            # If the substring has a length k then
            # increment count with current character
            if (cnt == k):
                curr += 1
 
        # Update max count
        maxSubStr = max(maxSubStr, curr)
 
    return maxSubStr
 
# Driver Code
if __name__ == '__main__':
    s = "aaacaabbaa"
    k = 2
    print(maxSubStrings(s, k))
 
# This code is contributed by
# Surendra_Gangwar

// C# implementation of the approach
using System;
 
class GFG
{
         
    // Function to return the count
    // of the required sub-strings
    static int maxSubStrings(String s, int k)
    {
        int maxSubStr = 0, n = s.Length;
     
        // Iterate over all characters
        for (int c = 0; c < 26; c++)
        {
            char ch = (char)((int)'a' + c);
     
            // Count with current character
            int curr = 0;
            for (int i = 0; i <= n - k; i++)
            {
                if (s[i] != ch)
                    continue;
                int cnt = 0;
                while (i < n && s[i] == ch &&
                                cnt != k)
                {
                    i++;
                    cnt++;
                }
                i--;
     
                // If the substring has a length
                // k then increment count with
                // current character
                if (cnt == k)
                    curr++;
            }
     
            // Update max count
            maxSubStr = Math.Max(maxSubStr, curr);
        }
        return maxSubStr;
    }
     
    // Driver Code
    public static void Main()
    {
        string s = "aaacaabbaa";
        int k = 2;
        Console.WriteLine(maxSubStrings(s, k));
    }
}
 
// This code is contributed by Ryuga

<script>
      // JavaScript implementation of the approach
      // Function to return the count
      // of the required sub-strings
      function maxSubStrings(s, k) {
        var maxSubStr = 0,
          n = s.length;
 
        // Iterate over all characters
        for (var c = 0; c < 26; c++) {
          var ch = String.fromCharCode("a".charCodeAt(0) + c);
 
          // Count with current character
          var curr = 0;
          for (var i = 0; i <= n - k; i++) {
            if (s[i] !== ch) continue;
            var cnt = 0;
            while (i < n && s[i] === ch && cnt !== k) {
              i++;
              cnt++;
            }
            i--;
 
            // If the substring has a length
            // k then increment count with
            // current character
            if (cnt === k) curr++;
          }
 
          // Update max count
          maxSubStr = Math.max(maxSubStr, curr);
        }
        return maxSubStr;
      }
 
      // Driver Code
      var s = "aaacaabbaa";
      var k = 2;
      document.write(maxSubStrings(s, k));
    </script>

3

Complejidad de tiempo: O(n), donde n es la longitud de la string.