Laske substrings k -erillisillä merkeillä
Kun otetaan huomioon merkkijono, joka koostuu vain pienistä englanninkielisistä kirjaimista ja kokonaisluku k laskee S: n alien kokonaismäärän (ei välttämättä erillisiä), jotka sisältävät tarkalleen K erilliset merkit.
Huomaa:
- Alku on vierekkäinen merkkisekvenssi merkkijonossa.
- Alusta, jotka ovat identtisiä, mutta jotka esiintyvät eri kohdissa, tulisi laskea erikseen.
Esimerkkejä:
Tulo: s = 'abc' k = 2
Lähtö: 2
Selitys: Mahdolliset alaryhmät ovat ['ab' 'bc']Tulo: s = 'aba' k = 2
Lähtö: 3
Selitys: Mahdolliset alaryhmät ovat ['ab' 'ba' 'aba']Tulo: s = 'aa' k = 1
Lähtö: 3
Selitys: Mahdolliset alaryhmät ovat ['a' 'a' 'aa']
Sisältötaulukko
- [Naiivi lähestymistapa] Kaikkien alusten tarkistaminen - o (n^2) aika ja o (1) tila
- [Tehokas lähestymistapa] liukukäyttöisen ikkunamenetelmän avulla - O (n) -aika ja O (1) -tila
[Naiivi lähestymistapa] Kaikkien alusten tarkistaminen - o (n^2) aika ja o (1) tila
C++Ajatuksena on tarkistaa kaikki mahdolliset alaryhmät iteroimalla kaikki mahdolliset lähtöasennot (i) ja pääteasennot (J) merkkijonossa. Jokaiselle alaryhmälle ylläpitä boolean taulukkoa erillisten merkkien seuraamiseksi ja erillisten merkkien lukumäärän laskurin seuraamiseksi. Kun se laajentaa alaosaa vasemmalta oikealle, se päivittää erillisen merkin määrän tarkistamalla, onko kukin uusi merkki ennen nähty. Aina kun erillisten merkkien lukumäärä vastaa tarkalleen annettua k: tä, se lisää vastauksen.
#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 ));
Tulos
2
[Tehokas lähestymistapa] liukukäyttöisen ikkunamenetelmän avulla - O (n) -aika ja O (1) -tila
Ajatuksena on käyttää liuku Tekniikka, jolla voidaan määrittää tehokkaasti substrenssit korkeintaan k-erillisillä merkkeillä ja vähentävät sitten alakohtaisten alaryhmien lukumäärän, jolla on korkeintaan K-1 erilliset merkit, jotta saadaan alien lukumäärä tarkalleen K erillisillä merkkeillä.
Askel askeleelta toteutus:
- Käytä liukuvaa ikkunaa, jonka koko on 26, merkkitaajuuksien seuraamiseksi.
- Laajenna ikkuna oikeaan lisäämään merkkejä.
- Kutista ikkuna vasemmalta, kun erilliset merkit ylittävät k.
- Laske kaikki kelvolliset alaryhmät ikkunassa.
- Vähennä alat K-1 erilliset merkit k-erillisistä merkeistä.
#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 ));
Tulos
2
