logo

TechCodeview

k개의 고유 문자가 포함된 하위 문자열 계산

영어 소문자로만 구성된 문자열 s와 정수 k가 주어지면 정확히 k개의 고유 문자를 포함하는 s의 하위 문자열(반드시 고유할 필요는 없음)의 총 개수를 계산합니다.
메모:

  • 하위 문자열은 문자열 내의 연속적인 문자 시퀀스입니다.
  • 동일하지만 다른 위치에서 발생하는 하위 문자열은 각각 별도로 계산되어야 합니다.

예:  



입력: s = 'abc' k = 2
산출: 2
설명: 가능한 하위 문자열은 ['ab' 'bc']입니다.

입력: s = '아바' k = 2
산출: 3
설명: 가능한 하위 문자열은 ['ab' 'ba' 'aba']입니다.

t 플립플롭

입력: s = 'AA' k = 1
산출: 3
설명: 가능한 하위 문자열은 ['a' 'a' 'aa']입니다.



목차

[순진한 접근 방식] 모든 하위 문자열 확인 - O(n^2) 시간 및 O(1) 공간

문자열에서 가능한 모든 시작 위치(i)와 끝 위치(j)를 반복하여 가능한 모든 하위 문자열을 확인하는 것이 아이디어입니다. 각 하위 문자열에 대해 고유 문자를 추적하는 부울 배열과 고유 문자 수에 대한 카운터를 유지합니다. 하위 문자열을 왼쪽에서 오른쪽으로 확장하면서 각 새 문자가 이전에 표시되었는지 확인하여 고유 문자 수를 업데이트합니다. 고유 문자 수가 주어진 k와 정확히 일치할 때마다 답변 수가 증가합니다.

버블 정렬 파이썬
C++ 
#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));

산출 
2

[효율적인 접근 방법] 슬라이딩 윈도우 방식을 이용한 O(n) 시간과 O(1) 공간

아이디어는 사용하는 것입니다 슬라이딩 윈도우 최대 k개의 고유 문자가 포함된 하위 문자열을 효율적으로 계산한 다음 최대 k-1개의 고유 문자가 포함된 하위 문자열의 개수를 빼서 정확히 k개의 고유 문자가 포함된 하위 문자열의 수를 얻는 기술입니다.



단계별 구현:

  • 문자 빈도를 추적하려면 크기가 26인 배열의 슬라이딩 창을 사용하세요.
  • 문자를 추가하여 창을 오른쪽으로 확장합니다.
  • 고유 문자가 k를 초과하면 왼쪽에서 창을 축소합니다.
  • 창 내에서 유효한 하위 문자열을 모두 계산합니다.
  • k개의 고유 문자에서 k-1개의 고유 문자가 포함된 하위 문자열을 뺍니다.
C++ 
#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));

산출 
2