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:
merkkijono vertaa c#
- 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']
unix luo hakemiston
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
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)); } }
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))
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)); } }
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ä.
"abc" on numeroissa
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
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)); } }
# 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))
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)); } }
// 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