Telle underlag med K -distinkte tegn
Gitt en streng som består av bare små bokstaver og et heltall k teller det totale antallet underlag (ikke nødvendigvis distinkte) av s som inneholder nøyaktig k distinkte tegn.
Note:
- En substring er en sammenhengende sekvens av tegn i en streng.
- Substrlinger som er identiske, men forekommer i forskjellige posisjoner, bør telles hver for seg.
Eksempler:
: s = 'abc' k = 2
Produksjon: 2
Forklaring: Mulige underlag er ['AB' 'BC']: s = 'aba' k = 2
Produksjon: 3
Forklaring: Mulige underlag er ['ab' 'ba' 'aba']: s = 'aa' k = 1
Produksjon: 3
Forklaring: Mulige underlag er ['A' 'A' 'AA']
Tabell over innhold
- [Naiv tilnærming] Kontroller alle underlag - O (N^2) Tid og O (1) plass
- [Effektiv tilnærming] Bruke glidende vindusmetode - o (n) tid og o (1) plass
[Naiv tilnærming] Kontroller alle underlag - O (N^2) Tid og O (1) plass
C++Tanken er å sjekke alle mulige substring ved å iterere gjennom alle mulige startposisjoner (I) og sluttposisjoner (J) i strengen. For hver substring opprettholder en boolsk matrise for å spore distinkte tegn og en teller for antall distinkte tegn. Når den utvider substringen fra venstre mot høyre, oppdaterer den det distinkte karaktertellingen ved å sjekke om hvert nye tegn har blitt sett før. Hver gang antallet distinkte karakterer nøyaktig samsvarer med de gitte k, øker det svaretellingen.
#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 ));
Produksjon
2
[Effektiv tilnærming] Bruke glidende vindusmetode - o (n) tid og o (1) plass
Tanken er å bruke skyve vindu Teknikk for å effektivt telle underlag med høyst K-distinkte tegn og deretter trekke tellingen av underlag med høyst K-1 distinkte tegn for å oppnå antall underlag med nøyaktig K distinkte tegn.
Trinn for trinns implementering:
- Bruk et skyvevindu med en rekke størrelse 26 for å spore karakterfrekvenser.
- Utvid vinduet til høyre og legge til tegn.
- Krymp vinduet fra venstre når distinkte tegn overstiger k.
- Tell alle gyldige underlag i vinduet.
- Trekk underlag med K-1 distinkte tegn fra K-distinkte 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 ));
Produksjon
2
