Given a string str of length n. The problem is to find the length of the longest sub-string in str having frequency of each character less than equal to the given value k.
Examples :
Input : str = "babcaag", k = 1 Output : 3 abc and bca are the two longest sub-strings having frequency of each character in them less than equal to '1'. Input : str = "neveropen", k = 2 Output : 10
Approach: Create an array freq[] of size 26 implemented as hash table to store the frequency of each character of str. Initialize all of its indexes with value ‘0’. Length of the string is n. Now implement the following algorithm.
longSubstring(str, k)
Initialize start = 0
Initialize maxLen = 0
Declare ch
for i = 0 to n-1
ch = str[i]
freq[ch - 'a']++
if k < freq[ch - 'a'] then
if maxLen < (i - start) then
maxLen = i - start
while (k < freq[ch - 'a'])
freq[str[start] - 'a']--
start++
if maxLen < (n - start) then
maxLen = n - start
return maxLen
Implementation:
C++
// C++ implementation to find// the length of the longest // substring having frequency// of each character less // than equal to k#include <bits/stdc++.h>using namespace std;#define SIZE 26// function to find the length// of the longest substring // having frequency of each // character less than equal // to kint longSubstring(string str, int k){ // hash table to store frequency // of each table int freq[SIZE]; // Initialize memset(freq, 0, sizeof(freq)); // 'start' index of the current // substring int start = 0; // to store the maximum length int maxLen = 0; char ch; int n = str.size(); // traverse the string 'str' for (int i = 0; i < n; i++) { // get the current character // as 'ch' ch = str[i]; // increase frequency of // 'ch' in 'freq[]' freq[ch - 'a']++; // if frequency of 'ch' becomes // more than 'k' if (freq[ch - 'a'] > k) { // update 'maxLen' if (maxLen < (i - start)) maxLen = i - start; // decrease frequency of // each character as they // are encountered from // the 'start' index until // frequency of 'ch' is // greater than 'k' while (freq[ch - 'a'] > k) { // decrement frequency // by '1' freq[str[start] - 'a']--; // increment 'start' start++; } } } // update maxLen if (maxLen < (n - start)) maxLen = n - start; // required length return maxLen;}// Driver program to test aboveint main(){ string str = "babcaag"; int k = 1; cout << "Length = " << longSubstring(str, k); return 0;} |
Java
// Java implementation to find// the length of the longest // substring having frequency// of each character less // than equal to kimport java.util.*;import java.lang.*;public class GfG{ public final static int SIZE = 26; // function to find the length // of the longest substring // having frequency of each // character less than equal // to k public static int longSubstring(String str1, int k) { // hash table to store frequency // of each table int[] freq = new int [SIZE]; char[] str = str1.toCharArray(); // 'start' index of the current // substring int start = 0; // to store the maximum length int maxLen = 0; char ch; int n = str1.length(); // traverse the string 'str' for (int i = 0; i < n; i++) { // get the current character // as 'ch' ch = str[i]; // increase frequency of // 'ch' in 'freq[]' freq[ch - 'a']++; // if frequency of 'ch' // becomes more than 'k' if (freq[ch - 'a'] > k) { // update 'maxLen' if (maxLen < (i - start)) maxLen = i - start; // decrease frequency of // each character as they // are encountered from // the 'start' index until // frequency of 'ch' is // greater than 'k' while (freq[ch - 'a'] > k) { // decrement frequency // by '1' freq[str[start] - 'a']--; // increment 'start' start++; } } } // update maxLen if (maxLen < (n - start)) maxLen = n - start; // required length return maxLen; } // Driver function public static void main(String argc[]) { String str = "babcaag"; int k = 1; System.out.println("Length = " + longSubstring(str, k)); }}/* This code is contributed by Sagar Shukla */ |
Python3
# Python3 implementation to find# the length of the longest # substring having frequency# of each character less than # equal to k# import libraryimport numpy as npSIZE = 26# Function to find the length# of the longest sub having# frequency of each character# less than equal to kdef longSub(str, k): # Hash table to store frequency # of each table freq = np.zeros(26, dtype = np.int ) # 'start' index of the # current substring start = 0 # To store the maximum length maxLen = 0 n = len(str) # Traverse the 'str' for i in range(0, n): # Get the current character # as 'ch' ch = str[i] # Increase frequency of # 'ch' in 'freq[]' freq[ord(ch) - ord('a') ] += 1 # If frequency of 'ch' # becomes more than 'k' if (freq[ord(ch) - ord('a')] > k): # update 'maxLen' if (maxLen < (i - start)): maxLen = i - start # decrease frequency of # each character as they # are encountered from # the 'start' index until # frequency of 'ch' is # greater than 'k' while (freq[ord(ch) - ord('a')] > k): # decrement frequency # by '1' freq[ord(str[start]) - ord('a')] -= 1 # increment 'start' start = start + 1 # Update maxLen if (maxLen < (n - start)): maxLen = n - start # required length return maxLen;# Driver Codestr = "babcaag"k = 1print ("Length =", longSub(str, k)) # This code is contributed by 'saloni1297' |
C#
// C# implementation to find// the length of the longest // substring having frequency// of each character less // than equal to kusing System;class GfG{ public static int SIZE = 26; // function to find the length // of the longest substring // having frequency of each // character less than equal // to k public static int longSubstring(String str1, int k) { // hash table to store // frequency of each table int []freq = new int [SIZE]; char []str = str1.ToCharArray(); // 'start' index of the // current substring int start = 0; // to store the maximum length int maxLen = 0; char ch; int n = str1.Length; // traverse the string 'str' for (int i = 0; i < n; i++) { // get the current character // as 'ch' ch = str[i]; // increase frequency of // 'ch' in 'freq[]' freq[ch - 'a']++; // if frequency of 'ch' // becomes more than 'k' if (freq[ch - 'a'] > k) { // update 'maxLen' if (maxLen < (i - start)) maxLen = i - start; // decrease frequency of // each character as they // are encountered from // the 'start' index until // frequency of 'ch' is // greater than 'k' while (freq[ch - 'a'] > k) { // decrement frequency // by '1' freq[str[start] - 'a']--; // increment 'start' start++; } } } // update maxLen if (maxLen < (n - start)) maxLen = n - start; // required length return maxLen; } // Driver function public static void Main() { String str = "babcaag"; int k = 1; Console.Write("Length = " + longSubstring(str, k)); }}// This code is contributed by nitin mittal |
PHP
<?php// PHP implementation to find// the length of the longest // sub$having frequency// of each character less // than equal to k$SIZE = 26;// function to find the length// of the longest sub$// having frequency of each // character less than equal // to kfunction longSubstring($str, $k){ global $SIZE; // hash table to // store frequency // of each table $freq = array(); // Initialize for($i = 0; $i < $SIZE; $i++) $freq[$i] = 0; // 'start' index of // the current substring $start = 0; // to store the // maximum length $maxLen = 0; $ch = ''; $n = strlen($str); // traverse the $'str' for ($i = 0; $i < $n; $i++) { // get the current // character as 'ch' $ch = $str[$i]; // increase frequency // of 'ch' in 'freq[]' $freq[ord($ch) - ord('a')]++; // if frequency of // 'ch' becomes // more than 'k' if ($freq[ord($ch) - ord('a')] > $k) { // update 'maxLen' if ($maxLen < ($i - $start)) $maxLen = $i - $start; // decrease frequency of // each character as they // are encountered from // the 'start' index until // frequency of 'ch' is // greater than 'k' while ($freq[ord($ch) - ord('a')] > $k) { // decrement frequency // by '1' $freq[ord($str[$start]) - ord('a')]--; // increment 'start' $start++; } } } // update maxLen if ($maxLen < ($n - $start)) $maxLen = $n - $start; // required length return $maxLen;}// Driver Code$str = "babcaag";$k = 1;echo ("Length = " . longSubstring($str, $k));// This code is contributed by // Manish Shaw(manishshaw1)?> |
Javascript
<script>// JavaScript implementation to find// the length of the longest // substring having frequency// of each character less // than equal to kvar SIZE = 26;// function to find the length// of the longest substring // having frequency of each // character less than equal // to kfunction longSubstring(str, k){ // hash table to store frequency // of each table var freq = Array(SIZE).fill(0); // 'start' index of the current // substring var start = 0; // to store the maximum length var maxLen = 0; var ch; var n = str.length; // traverse the string 'str' for (var i = 0; i < n; i++) { // get the current character // as 'ch' ch = str[i]; // increase frequency of // 'ch' in 'freq[]' freq[ch.charCodeAt(0) - 'a'.charCodeAt(0)]++; // if frequency of 'ch' becomes // more than 'k' if (freq[ch.charCodeAt(0) - 'a'.charCodeAt(0)] > k) { // update 'maxLen' if (maxLen < (i - start)) maxLen = i - start; // decrease frequency of // each character as they // are encountered from // the 'start' index until // frequency of 'ch' is // greater than 'k' while (freq[ch.charCodeAt(0) - 'a'.charCodeAt(0)] > k) { // decrement frequency // by '1' freq[str[start].charCodeAt(0) - 'a'.charCodeAt(0)]--; // increment 'start' start++; } } } // update maxLen if (maxLen < (n - start)) maxLen = n - start; // required length return maxLen;}// Driver program to test abovevar str = "babcaag";var k = 1;document.write( "Length = " + longSubstring(str, k));</script> |
Output
Length = 3
Time Complexity: O(n).
Auxiliary Space: O(1).
Because of the while loop the complexity might seem quadratic but if we look closely the inner while loop will traverse the string single time only.”
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!
