Given a string ‘str’ and an integer ‘k’, the task is to count the number of sub-strings of length ‘k’ which are comprised of the same character. Given string contains only lowercase alphabets.
Examples:
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
A simple approach:
- Find all the sub-strings of the string that are of length ‘k’.
- Check if those sub-strings are composed of only ‘1’ character.
- If the above conditions hold then increase the count.
- Display the count.
Efficient approach: We will use Window sliding technique to solve this problem.
- Take a sub-string of length ‘k’ (which is the first ‘k’ characters).
- Then, add next character to the sub-string.
- If the length of the sub-string is greater than ‘k’ then remove the character from the beginning of the string.
- And, count the frequency of the characters in the sub-string with the help of a map.
- If the frequency of one of the sub-string’s character is equal to length of the sub-string itself i.e. all the characters are same.
- Then, increase the count else repeat the steps above until the there’s no more character to add in the end.
- Display the total count in the end.
Below is the implementation of the above approach :
C++
// 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 charactersvoid 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 codeint main(){ string s = "aaaabbbccdddd"; int k = 4; solve(s, k); return 0;} |
Java
// Java implementation of above approachimport 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 |
Python 3
# Python3 implementation of above # approach# Function that counts all the # sub-strings of length 'k' # which have all identical charactersdef 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#
// C# implementation of above approachusing 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 // PHP implementation of above approach// Function that counts all the// sub-strings of length 'k'// which have all identical charactersfunction 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?> |
Javascript
<script>// Javascript implementation of above approach// Function that counts all the// sub-strings of length 'k'// which have all identical charactersfunction 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 codevar s = "aaaabbbccdddd";var k = 4;solve(s, k);</script> |
2
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

… [Trackback]
[…] Read More to that Topic: geeksforgeeks.org/sub-strings-of-length-k-containing-same-character/ […]
… [Trackback]
[…] Find More Information here on that Topic: geeksforgeeks.org/sub-strings-of-length-k-containing-same-character/ […]
… [Trackback]
[…] There you will find 73789 additional Info on that Topic: geeksforgeeks.org/sub-strings-of-length-k-containing-same-character/ […]
… [Trackback]
[…] Find More on on that Topic: geeksforgeeks.org/sub-strings-of-length-k-containing-same-character/ […]