Maximum count of sub-strings of length K consisting of same characters

0 0 5 minutes read

Given a string str and an integer k. The task is to count the occurrences of sub-strings of length k that consist of the same characters. There can be multiple such sub-strings possible of length k, choose the count of the one which appears the maximum number of times as the sub-string (non-overlapping) of str.

Examples:

Input: str = “aaacaabbaa”, k = 2
Output: 3
“aa” and “bb” are the only sub-strings of length 2 that consist of the same characters.
“bb” appears only once as a sub-string of str whereas “aa” appears thrice (which is the answer)

Input: str = “abab”, k = 2
Output: 0

Approach: Iterate over all the characters from ‘a’ to ‘z’ and count the number of times a string of length k consisting only of the current character appears as a sub-string of str. Print the maximum of these counts in the end.

Steps to solve the problem:

Initialize maxSubStr to 0 and n to the size of the string s.
Iterate over all characters of the English alphabet using a loop from 0 to 25.
For each character, store it in a variable ch.
Initialize a variable curr to 0.
Use another loop to iterate over all possible substrings of length k in the string s.
If the current character of the string s is not the same as the character ch, continue with the next iteration of the loop.
If the current character is the same as ch, count the number of consecutive characters in the substring that are the same as ch, using a variable cnt.
If cnt is not equal to k, continue with the next iteration of the loop.
If cnt is equal to k, increment the variable curr.
After the inner loop, update maxSubStr to the maximum of its current value and curr.
After the outer loop, return maxSubStr as the result.

Below is the implementation of the above approach:

C++

// 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

// 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

Python3

# 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#

// 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

Javascript

<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>

Output

Time Complexity: O(n), where n is the length of the string.
Auxiliary Space: O(1).

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 zambiatek!