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-stringsint 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 Codeint main(){ string s = "aaacaabbaa"; int k = 2; cout << maxSubStrings(s, k); return 0;} |
Java
// Java implementation of the approachimport java.util.*;import java.lang.*;import java.io.*;class GFG{ // Function to return the count// of the required sub-stringsstatic 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 Codepublic 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-stringsdef 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 Codeif __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
3
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
