给一根绳子 str 长度 N .问题是要找出最长子字符串的长度 str 每个字符的频率小于等于给定值的 K . 例如：
null
Input : str = "babcaag", k = 1Output : 3abc and bca are the two longestsub-strings having frequency of each character in them less than equal to '1'.Input : str = "geeksforgeeks", k = 2Output : 10
方法： 创建一个数组 频率[] 大小为26的，实现为哈希表，用于存储 str 。使用值“0”初始化其所有索引。绳子的长度是 N .现在实现以下算法。
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
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 k int 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 above int 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 k import 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 library import numpy as np SIZE = 26 # Function to find the length # of the longest sub having # frequency of each character # less than equal to k def 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 Code str = "babcaag" k = 1 print ( "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 k using 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 k function 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 k var SIZE = 26; // function to find the length // of the longest substring // having frequency of each // character less than equal // to k function 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 above var str = "babcaag" ; var k = 1; document.write( "Length = " + longSubstring(str, k)); </script> |
输出：
Length = 3
时间复杂性： O（n）。 辅助空间： O（1）。 由于while循环，复杂性可能看起来是二次的，但如果我们仔细观察内部while循环，它只会遍历字符串一次。”
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
