Substrings de longitud K que contienen el mismo carácter

Dada una string ‘str’ y un entero ‘k’, la tarea es contar el número de substrings de longitud ‘k’ que se componen del mismo carácter. La string dada contiene solo alfabetos en minúsculas.
Ejemplos: 
 

Input: str = "aaaabbbccdddd", k=4
Output: 2
The sub-strings of length 4 which contain identical 
characters are 'aaaa' and 'dddd'. So, the count is 2.

Input: str = "aaaaaa", k=4
Output: 3

Un enfoque simple: 
 

• Encuentre todas las substrings de la string que tienen una longitud de ‘k’.
• Compruebe si esas substrings están compuestas solo por el carácter ‘1’.
• Si se cumplen las condiciones anteriores, aumente el conteo.
• Mostrar el conteo.

Enfoque eficiente: utilizaremos la técnica de deslizamiento de ventanas para resolver este problema. 
 

• Tome una substring de longitud ‘k’ (que son los primeros caracteres ‘k’).
• Luego, agregue el siguiente carácter a la substring.
• Si la longitud de la substring es mayor que ‘k’, elimine el carácter del principio de la string.
• Y cuente la frecuencia de los caracteres en la substring con la ayuda de un mapa.
• Si la frecuencia de uno de los caracteres de la substring es igual a la longitud de la propia substring, es decir, todos los caracteres son iguales.
• Luego, aumente el conteo; de lo contrario, repita los pasos anteriores hasta que no haya más caracteres para agregar al final.
• Muestra el recuento total al final.

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

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that counts all the
// sub-strings of length 'k'
// which have all identical characters
void solve(string s, int k)
{
    // count of sub-strings, length,
    // initial position of sliding window
    int count = 0, length = 0, pos = 0;
 
    // map to store the frequency of
    // the characters of sub-string
    map<char, int> m;
 
    for (int i = 0; i < s.length(); i++) {
 
        // increase the frequency of the character
        // and length of the sub-string
        m[s[i]]++;
        length++;
 
        // if the length of the sub-string
        // is greater than K
        if (length > k) {
 
            // remove the character from
            // the beginning of sub-string
            m[s[pos++]]--;
            length--;
        }
 
        // if the length of the sub string
        // is equal to k and frequency of one
        // of its characters is equal to the
        // length of the sub-string
        // i.e. all the characters are same
        // increase the count
        if (length == k && m[s[i]] == length)
            count++;
    }
 
    // display the number
    // of valid sub-strings
    cout << count << endl;
}
 
// Driver code
int main()
{
    string s = "aaaabbbccdddd";
    int k = 4;
 
    solve(s, k);
 
    return 0;
}

// Java implementation of above approach
import java.util.*;
 
class GFG
{
    // Function that counts all the
    // sub-strings of length 'k'
    // which have all identical characters
    static void solve(String s, int k)
    {
        // count of sub-strings, length,
        // initial position of sliding window
        int count = 0, length = 0, pos = 0;
     
        // map to store the frequency of
        // the characters of sub-string
        HashMap<Character, Integer> m =
                            new HashMap<Character, Integer>();
     
        for (int i = 0; i < s.length(); i++)
        {
     
            // increase the frequency of the character
            // and length of the sub-string
            if(m.containsKey(s.charAt(i)))
                m.put(s.charAt(i), m.get(s.charAt(i))+1);
            else
                m.put(s.charAt(i), 1);
                 
            length++;
     
            // if the length of the sub-string
            // is greater than K
            if (length > k)
            {
     
                // remove the character from
                // the beginning of sub-string
                m.put(s.charAt(pos), m.get(s.charAt(pos)) -1 );
                pos++;
                length--;
            }
     
            // if the length of the sub string
            // is equal to k and frequency of one
            // of its characters is equal to the
            // length of the sub-string
            // i.e. all the characters are same
            // increase the count
            if (length == k && m.get(s.charAt(i)) == length)
                count++;
        }
     
        // display the number
        // of valid sub-strings
        System.out.println( count);
    }
     
    // Driver code
    public static void main (String[] args)
    {
         
        String s = "aaaabbbccdddd";
        int k = 4;
     
        solve(s, k);
    }
}
 
// This code is contributed by ihritik

# Python3 implementation of above
# approach
 
# Function that counts all the
# sub-strings of length 'k'
# which have all identical characters
def solve(s, k) :
 
    # count of sub-strings, length,
    # initial position of sliding window
    count, length, pos = 0, 0, 0
 
    # dictionary to store the frequency of
    # the characters of sub-string
    m = dict.fromkeys(s,0)
 
    for i in range(len(s)) :
         
        # increase the frequency of the character
        # and length of the sub-string
        m[s[i]] += 1
        length += 1
 
        # if the length of the sub-string
        # is greater than K
        if length > k :
 
            # remove the character from
            # the beginning of sub-string
            m[s[pos]] -= 1
            pos += 1
            length -= 1
 
        # if the length of the sub string
        # is equal to k and frequency of one
        # of its characters is equal to the
        # length of the sub-string
        # i.e. all the characters are same
        # increase the count
        if length == k and m[s[i]] == length :
            count += 1
 
    # display the number
    # of valid sub-strings
    print(count)
             
 
 
# Driver code    
if __name__ == "__main__" :
 
    s = "aaaabbbccdddd"
    k = 4
 
    # Function call
    solve(s, k)
                 
# This code is contributed by
# ANKITRAI1

// C# implementation of above approach
 
using System;
using System.Collections.Generic;
class GFG
{
    // Function that counts all the
    // sub-strings of length 'k'
    // which have all identical characters
    static void solve(string s, int k)
    {
        // count of sub-strings, length,
        // initial position of sliding window
        int count = 0, length = 0, pos = 0;
     
        // map to store the frequency of
        // the characters of sub-string
        Dictionary<char, int> m =
                            new Dictionary<char, int>();
     
        for (int i = 0; i < s.Length; i++) {
     
            // increase the frequency of the character
            // and length of the sub-string
            if(m.ContainsKey(s[i]))
                m[s[i]]++;
            else
                m[s[i]] = 1;
                 
            length++;
     
            // if the length of the sub-string
            // is greater than K
            if (length > k) {
     
                // remove the character from
                // the beginning of sub-string
                m[s[pos]]--;
                pos++;
                length--;
            }
     
            // if the length of the sub string
            // is equal to k and frequency of one
            // of its characters is equal to the
            // length of the sub-string
            // i.e. all the characters are same
            // increase the count
            if (length == k && m[s[i]] == length)
                count++;
        }
     
        // display the number
        // of valid sub-strings
        Console.WriteLine(count);
    }
     
    // Driver code
    public static void Main () {
         
        string s = "aaaabbbccdddd";
        int k = 4;
     
        solve(s, k);
     
    }
 
}
 
 
// This code is contributed by ihritik

<?php
// PHP implementation of above approach
 
// Function that counts all the
// sub-strings of length 'k'
// which have all identical characters
function solve($s, $k)
{
    // count of sub-strings, length,
    // initial position of sliding window
    $count = 0;
    $length = 0;
    $pos = 0;
 
    // map to store the frequency of
    // the characters of sub-string
    $m = array();
 
    for ($i = 0; $i < strlen($s); $i++)
    {
 
        // increase the frequency of the character
        // and length of the sub-string
        $m[$s[$i]]++;
        $length++;
 
        // if the length of the sub-string
        // is greater than K
        if ($length > $k)
        {
 
            // remove the character from
            // the beginning of sub-string
            $m[$s[$pos++]]--;
            $length--;
        }
 
        // if the length of the sub string
        // is equal to k and frequency of one
        // of its characters is equal to the
        // length of the sub-string
        // i.e. all the characters are same
        // increase the count
        if ($length == $k && $m[$s[$i]] == $length)
            $count++;
    }
 
    // display the number
    // of valid sub-strings
    echo $count . "\n";
}
 
// Driver code
$s = "aaaabbbccdddd";
$k = 4;
 
solve($s, $k);
 
// This code is contributed
// by ChitraNayal
?>

<script>
 
 
// Javascript implementation of above approach
 
// Function that counts all the
// sub-strings of length 'k'
// which have all identical characters
function solve( s,  k)
{
    // count of sub-strings, length,
    // initial position of sliding window
    var count = 0, length = 0, pos = 0;
 
    // map to store the frequency of
    // the characters of sub-string
    var m = new Map();
 
    for (var i = 0; i < s.length; i++) {
 
        // increase the frequency of the character
        // and length of the sub-string
        if(!m.has(s[i]))
        {
            m.set(s[i], 0);
        }
        m.set(s[i], m.get(s[i])+1);
        length++;
 
        // if the length of the sub-string
        // is greater than K
        if (length > k) {
 
            // remove the character from
            // the beginning of sub-string
            if(!m.has(s[pos]))
            {
                m.set(s[pos], 0);
            }
            m.set(s[pos], m[s[pos]]-1);
            pos+=1;
            length--;
        }
 
        // if the length of the sub string
        // is equal to k and frequency of one
        // of its characters is equal to the
        // length of the sub-string
        // i.e. all the characters are same
        // increase the count
        if (length == k && m.get(s[i]) == length)
            count++;
    }
 
    // display the number
    // of valid sub-strings
    document.write( count);
}
 
// Driver code
var s = "aaaabbbccdddd";
var k = 4;
solve(s, k);
 
 
</script>

2