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> |
Output
2
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
