k-1개의 개별 요소가 있는 길이 k의 하위 문자열
문제 설명
소문자 알파벳과 정수 K로만 구성된 문자열 S가 주어집니다. 정확히 K-1개의 개별 문자를 갖는 길이 K의 모든 부분 문자열의 수를 찾으십시오.
문제 설명 링크::https://practice.geeksforgeeks.org/problems/substrings-of-length-k-with-k-1-distinct-elements/1
Example 1:
Input:
S = "abcc"
K = 2
Output:
1
Explanation:
Possible substrings of length K = 2 are
ab : 2 distinct characters
bc : 2 distinct characters
cc : 1 distinct character
Only one valid substring exists {"cc"}.
Example 2:
Input:
S = "aabab"
K = 3
Output :
3
Explanation:
Possible substrings of length K = 3 are
aab : 2 distinct characters
aba : 2 distinct characters
bab : 2 distinct characters.
All of these Substrings are a possible answer,
so the count is 3.
예상 시간 복잡도: O(|S|)
예상 보조 공간: O(1)
해결책
문제는 예상 문자열의 길이가 상수 K이므로 두 포인터의 도움으로 접근할 수 있습니다. 따라서 두 포인터 사이의 창은 left(l)와 right(*r)가 같고 이 창을 슬라이드하면 됩니다. 한 캐릭터씩.
슬라이딩은 이전 문자가 제거되고 새 문자가 포함됩니다. 이에 따라 문자표를 업데이트해야 합니다. 문자 맵은 창에서 빈도가 있는 문자를 유지 관리하는 맵입니다.
class Solution {
static int countOfSubstrings(String S, int k) {
char[] s = S.toCharArray();
int l = 0;
int r = 0;
int cnt = 0;
HashMap<Character, Integer> map = new HashMap<>();
// initial map setting for window
for(; r < k; r++) {
map.put(s[r], map.getOrDefault(s[r], 0) + 1);
}
int res = map.size() == k - 1? 1 : 0;
// gradually incrementing window
for (; r < s.length; r++, l++) {
// adding the character
map.put(s[r], map.getOrDefault(s[r], 0) + 1);
// removing character
if( map.get(s[l]) == 1 ) {
// remove character
// if it was the only character
// into the window
map.remove(s[l]);
} else {
map.put(s[l], map.get(s[l]) - 1);
}
if(map.size() == k-1) res++;
}
return res;
}
}
Reference
이 문제에 관하여(k-1개의 개별 요소가 있는 길이 k의 하위 문자열), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/obrutus/substring-of-length-k-with-k-1-distinct-elements-h2e텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)