K farklı karaktere sahip alt dizeleri sayın
Yalnızca küçük İngilizce harflerden ve bir k tam sayısından oluşan bir dize verildiğinde, tam olarak k farklı karakter içeren s'nin alt dizelerinin (farklı olması gerekmez) toplam sayısı sayılır.
Not:
- Bir alt dize, bir dize içindeki bitişik karakter dizisidir.
- Aynı olan ancak farklı konumlarda meydana gelen alt dizelerin her biri ayrı ayrı sayılmalıdır.
Örnekler:
Giriş: s = 'abc' k = 2
Çıkış: 2
Açıklama: Olası alt dizeler şunlardır: ['ab' 'bc']Giriş: s = 'aba' k = 2
Çıkış: 3
Açıklama: Olası alt dizeler şunlardır: ['ab' 'ba' 'aba']Giriş: s = 'AA' k = 1
Çıkış: 3
Açıklama: Olası alt dizeler şunlardır: ['a' 'a' 'aa']
İçerik Tablosu
- [Naif Yaklaşım] Tüm Alt Dizileri Kontrol Etme - O(n^2) zaman ve O(1) uzay
- [Etkili Yaklaşım] Kayan Pencere Yöntemini Kullanma - O(n) zamanı ve O(1) alanı
[Naif Yaklaşım] Tüm Alt Dizileri Kontrol Etme - O(n^2) zaman ve O(1) uzay
C++Buradaki fikir, dizedeki tüm olası başlangıç konumlarını (i) ve bitiş konumlarını (j) yineleyerek olası her alt diziyi kontrol etmektir. Her bir alt dize için, farklı karakterleri izlemek üzere bir boole dizisi ve farklı karakterlerin sayısı için bir sayaç bulundurun. Alt dizeyi soldan sağa genişletirken, her yeni karakterin daha önce görülüp görülmediğini kontrol ederek farklı karakter sayısını günceller. Farklı karakterlerin sayısı verilen k ile tam olarak eşleştiğinde cevap sayısı artar.
#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 ));
Çıkış
2
[Etkili Yaklaşım] Kayan Pencere Yöntemini Kullanma - O(n) zamanı ve O(1) alanı
Fikir kullanmaktır sürgülü pencere En fazla k farklı karaktere sahip alt dizileri verimli bir şekilde sayma ve ardından tam olarak k farklı karaktere sahip alt dizilerin sayısını elde etmek için en fazla k-1 farklı karaktere sahip alt dizilerin sayısını çıkarma tekniği.
Adım Adım Uygulama:
- Karakter frekanslarını izlemek için 26 boyutlu bir diziye sahip kayan bir pencere kullanın.
- Karakterleri ekleyerek pencereyi sağa doğru genişletin.
- Farklı karakterler k değerini aştığında pencereyi soldan daraltın.
- Penceredeki tüm geçerli alt dizeleri sayın.
- k-1 farklı karakter içeren alt dizeleri k farklı karakterden çıkarın.
#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 ));
Çıkış
2
