Tæl substrenge med k forskellige tegn
Givet en streng, der består af kun små bogstaver og et heltal K, tæller det samlede antal understrenge (ikke nødvendigvis forskellige) af S, der indeholder nøjagtigt k forskellige tegn.
Note:
- En substring er en sammenhængende sekvens af tegn i en streng.
- Substrings, der er identiske, men forekommer i forskellige positioner, bør hver især tælles separat.
Eksempler:
Input: s = 'abc' k = 2
Produktion: 2
Forklaring: Mulige substrings er ['ab' 'bc']Input: s = 'aba' k = 2
Produktion: 3
Forklaring: Mulige substrenge er ['ab' 'ba' 'aba']Input: s = 'aa' k = 1
Produktion: 3
Forklaring: Mulige substrings er ['a' 'a' 'aa']
Indholdstabel
- [Naiv tilgang] Kontrol af alle substrenge - O (n^2) Tid og O (1) Rum
- [Effektiv tilgang] Brug af skydevinduetemetode - O (n) Tid og O (1) Rum
[Naiv tilgang] Kontrol af alle substrenge - O (n^2) Tid og O (1) Rum
C++Ideen er at kontrollere enhver mulig substring ved at iterere gennem alle mulige startpositioner (I) og slutpositioner (J) i strengen. For hver substring skal du opretholde en boolsk matrix for at spore forskellige tegn og en tæller for antallet af forskellige tegn. Når det udvider substringen fra venstre til højre, opdaterer den det tydelige tegntælling ved at kontrollere, om hver nye karakter er blevet set før. Hver gang antallet af forskellige tegn svarer nøjagtigt til det givne k, øger det svartællingen.
#include #include using namespace std ; int countSubstr ( string & s int k ) { int n = s . length (); int ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) { // array to check if a character // is present in substring i..j vector < bool > map ( 26 0 ); int distinctCnt = 0 ; for ( int j = i ; j < n ; j ++ ) { // if new character is present // increment distinct count. if ( map [ s [ j ] - 'a' ] == false ) { map [ s [ j ] - 'a' ] = true ; distinctCnt ++ ; } // if distinct count is equal to k. if ( distinctCnt == k ) ans ++ ; } } return ans ; } int main () { string s = 'abc' ; int k = 2 ; cout < < countSubstr ( s k ); return 0 ; }
Java class GfG { static int countSubstr ( String s int k ) { int n = s . length (); int ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) { // array to check if a character // is present in substring i..j boolean [] map = new boolean [ 26 ] ; int distinctCnt = 0 ; for ( int j = i ; j < n ; j ++ ) { // if new character is present // increment distinct count. if ( ! map [ s . charAt ( j ) - 'a' ] ) { map [ s . charAt ( j ) - 'a' ] = true ; distinctCnt ++ ; } // if distinct count is equal to k. if ( distinctCnt == k ) ans ++ ; } } return ans ; } public static void main ( String [] args ) { String s = 'abc' ; int k = 2 ; System . out . println ( countSubstr ( s k )); } }
Python def countSubstr ( s k ): n = len ( s ) ans = 0 for i in range ( n ): # array to check if a character # is present in substring i..j map = [ False ] * 26 distinctCnt = 0 for j in range ( i n ): # if new character is present # increment distinct count. if not map [ ord ( s [ j ]) - ord ( 'a' )]: map [ ord ( s [ j ]) - ord ( 'a' )] = True distinctCnt += 1 # if distinct count is equal to k. if distinctCnt == k : ans += 1 return ans if __name__ == '__main__' : s = 'abc' k = 2 print ( countSubstr ( s k ))
C# using System ; class GfG { static int countSubstr ( string s int k ) { int n = s . Length ; int ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) { // array to check if a character // is present in substring i..j bool [] map = new bool [ 26 ]; int distinctCnt = 0 ; for ( int j = i ; j < n ; j ++ ) { // if new character is present // increment distinct count. if ( ! map [ s [ j ] - 'a' ]) { map [ s [ j ] - 'a' ] = true ; distinctCnt ++ ; } // if distinct count is equal to k. if ( distinctCnt == k ) ans ++ ; } } return ans ; } static void Main () { string s = 'abc' ; int k = 2 ; Console . WriteLine ( countSubstr ( s k )); } }
JavaScript function countSubstr ( s k ) { let n = s . length ; let ans = 0 ; for ( let i = 0 ; i < n ; i ++ ) { // array to check if a character // is present in substring i..j let map = new Array ( 26 ). fill ( false ); let distinctCnt = 0 ; for ( let j = i ; j < n ; j ++ ) { // if new character is present // increment distinct count. if ( ! map [ s . charCodeAt ( j ) - 'a' . charCodeAt ( 0 )]) { map [ s . charCodeAt ( j ) - 'a' . charCodeAt ( 0 )] = true ; distinctCnt ++ ; } // if distinct count is equal to k. if ( distinctCnt === k ) ans ++ ; } } return ans ; } // Driver Code let s = 'abc' ; let k = 2 ; console . log ( countSubstr ( s k ));
Produktion
2
[Effektiv tilgang] Brug af skydevinduetemetode - O (n) Tid og O (1) Rum
Ideen er at bruge glidende vindue Teknik til effektivt at tælle substrings med højst k forskellige tegn og trækker derefter tællingen af substrings med højst K-1 forskellige tegn for at opnå antallet af underlag med nøjagtigt k forskellige tegn.
Trin for trin implementering:
- Brug et glidevindue med en række størrelse 26 til at spore karakterfrekvenser.
- Udvid vinduet til højre tilføjelse af tegn.
- Krymp vinduet fra venstre, når forskellige tegn overstiger k.
- Tæl alle gyldige underlag i vinduet.
- Træk substrings med K-1 forskellige tegn fra K forskellige tegn.
#include #include using namespace std ; // function which finds the number of // substrings with atmost k Distinct // characters. int count ( string & s int k ) { int n = s . length (); int ans = 0 ; // use sliding window technique vector < int > freq ( 26 0 ); int distinctCnt = 0 ; int i = 0 ; for ( int j = 0 ; j < n ; j ++ ) { // expand window and add character freq [ s [ j ] - 'a' ] ++ ; if ( freq [ s [ j ] - 'a' ] == 1 ) distinctCnt ++ ; // shrink window if distinct characters exceed k while ( distinctCnt > k ) { freq [ s [ i ] - 'a' ] -- ; if ( freq [ s [ i ] - 'a' ] == 0 ) distinctCnt -- ; i ++ ; } // add number of valid substrings ending at j ans += j - i + 1 ; } return ans ; } // function to find the number of substrings // with exactly k Distinct characters. int countSubstr ( string & s int k ) { int n = s . length (); int ans = 0 ; // subtract substrings with at most // k-1 distinct characters from substrings // with at most k distinct characters ans = count ( s k ) - count ( s k -1 ); return ans ; } int main () { string s = 'abc' ; int k = 2 ; cout < < countSubstr ( s k ); return 0 ; }
Java class GfG { // function which finds the number of // substrings with atmost k Distinct // characters. static int count ( String s int k ) { int n = s . length (); int ans = 0 ; // use sliding window technique int [] freq = new int [ 26 ] ; int distinctCnt = 0 ; int i = 0 ; for ( int j = 0 ; j < n ; j ++ ) { // expand window and add character freq [ s . charAt ( j ) - 'a' ]++ ; if ( freq [ s . charAt ( j ) - 'a' ] == 1 ) distinctCnt ++ ; // shrink window if distinct characters exceed k while ( distinctCnt > k ) { freq [ s . charAt ( i ) - 'a' ]-- ; if ( freq [ s . charAt ( i ) - 'a' ] == 0 ) distinctCnt -- ; i ++ ; } // add number of valid substrings ending at j ans += j - i + 1 ; } return ans ; } // function to find the number of substrings // with exactly k Distinct characters. static int countSubstr ( String s int k ) { int n = s . length (); int ans = 0 ; // Subtract substrings with at most // k-1 distinct characters from substrings // with at most k distinct characters ans = count ( s k ) - count ( s k - 1 ); return ans ; } public static void main ( String [] args ) { String s = 'abc' ; int k = 2 ; System . out . println ( countSubstr ( s k )); } }
Python # function which finds the number of # substrings with atmost k Distinct # characters. def count ( s k ): n = len ( s ) ans = 0 # ese sliding window technique freq = [ 0 ] * 26 distinctCnt = 0 i = 0 for j in range ( n ): # expand window and add character freq [ ord ( s [ j ]) - ord ( 'a' )] += 1 if freq [ ord ( s [ j ]) - ord ( 'a' )] == 1 : distinctCnt += 1 # shrink window if distinct characters exceed k while distinctCnt > k : freq [ ord ( s [ i ]) - ord ( 'a' )] -= 1 if freq [ ord ( s [ i ]) - ord ( 'a' )] == 0 : distinctCnt -= 1 i += 1 # add number of valid substrings ending at j ans += j - i + 1 return ans # function to find the number of substrings # with exactly k Distinct characters. def countSubstr ( s k ): n = len ( s ) ans = 0 # subtract substrings with at most # k-1 distinct characters from substrings # with at most k distinct characters ans = count ( s k ) - count ( s k - 1 ) return ans if __name__ == '__main__' : s = 'abc' k = 2 print ( countSubstr ( s k ))
C# using System ; class GfG { // function which finds the number of // substrings with atmost k Distinct // characters. static int count ( string s int k ) { int n = s . Length ; int ans = 0 ; // use sliding window technique int [] freq = new int [ 26 ]; int distinctCnt = 0 ; int i = 0 ; for ( int j = 0 ; j < n ; j ++ ) { // expand window and add character freq [ s [ j ] - 'a' ] ++ ; if ( freq [ s [ j ] - 'a' ] == 1 ) distinctCnt ++ ; // shrink window if distinct characters exceed k while ( distinctCnt > k ) { freq [ s [ i ] - 'a' ] -- ; if ( freq [ s [ i ] - 'a' ] == 0 ) distinctCnt -- ; i ++ ; } // add number of valid substrings ending at j ans += j - i + 1 ; } return ans ; } // function to find the number of substrings // with exactly k Distinct characters. static int countSubstr ( string s int k ) { int n = s . Length ; int ans = 0 ; // subtract substrings with at most // k-1 distinct characters from substrings // with at most k distinct characters ans = count ( s k ) - count ( s k - 1 ); return ans ; } static void Main () { string s = 'abc' ; int k = 2 ; Console . WriteLine ( countSubstr ( s k )); } }
JavaScript // function which finds the number of // substrings with atmost k Distinct // characters. function count ( s k ) { let n = s . length ; let ans = 0 ; // use sliding window technique let freq = new Array ( 26 ). fill ( 0 ); let distinctCnt = 0 ; let i = 0 ; for ( let j = 0 ; j < n ; j ++ ) { // expand window and add character freq [ s . charCodeAt ( j ) - 'a' . charCodeAt ( 0 )] ++ ; if ( freq [ s . charCodeAt ( j ) - 'a' . charCodeAt ( 0 )] === 1 ) distinctCnt ++ ; // shrink window if distinct characters exceed k while ( distinctCnt > k ) { freq [ s . charCodeAt ( i ) - 'a' . charCodeAt ( 0 )] -- ; if ( freq [ s . charCodeAt ( i ) - 'a' . charCodeAt ( 0 )] === 0 ) distinctCnt -- ; i ++ ; } // add number of valid substrings ending at j ans += j - i + 1 ; } return ans ; } // sunction to find the number of substrings // with exactly k Distinct characters. function countSubstr ( s k ) { let n = s . length ; let ans = 0 ; // subtract substrings with at most // k-1 distinct characters from substrings // with at most k distinct characters ans = count ( s k ) - count ( s k - 1 ); return ans ; } // Driver Code let s = 'abc' ; let k = 2 ; console . log ( countSubstr ( s k ));
Produktion
2
![Top 10 mest magtfulde lande i verden efter militær styrke [2023]](https://techcodeview.com/img/current-gk/40/top-10-most-powerful-country-world-military-strength.webp)
