Description
You are given a string word
and an integer k
.
A substring s
of word
is complete if:
- Each character in
s
occurs exactlyk
times. - The difference between two adjacent characters is at most
2
. That is, for any two adjacent charactersc1
andc2
ins
, the absolute difference in their positions in the alphabet is at most2
.
Return the number of complete substrings of word
.
A substring is a non-empty contiguous sequence of characters in a string.
Example 1:
Input: word = "igigee", k = 2 Output: 3 Explanation: The complete substrings where each character appears exactly twice and the difference between adjacent characters is at most 2 are: igigee, igigee, igigee.
Example 2:
Input: word = "aaabbbccc", k = 3 Output: 6 Explanation: The complete substrings where each character appears exactly three times and the difference between adjacent characters is at most 2 are: aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc.
Constraints:
1 <= word.length <= 105
word
consists only of lowercase English letters.1 <= k <= word.length
Solution
Python3
class Solution:
def countCompleteSubstrings(self, word: str, k: int) -> int:
def f(x):
return ord(x) - ord('a')
def check(cnt, uniqueChars):
unique = 0
for x in cnt:
if x == 0: continue
if x != k: return False
unique += 1
return unique == uniqueChars
def solve(A):
M = len(A)
res = 0
# there are 26 unique characters, loop thru the len with k, 2k, 3k ..., 26k
for uniqueChars in range(1, 27):
length = k * uniqueChars
if length > M: break
cnt = [0] * 26
for i in range(length):
cnt[f(A[i])] += 1
res += check(cnt, uniqueChars)
# when length is greater than M, slide the window from (length - M, length)
for i in range(length, M):
cnt[f(A[i - length])] -= 1
cnt[f(A[i])] += 1
res += check(cnt, uniqueChars)
return res
N = len(word)
res = 0
curr = ""
for i, x in enumerate(word):
curr += x
if i < N - 1 and abs(ord(word[i + 1]) - ord(word[i])) > 2:
res += solve(curr)
curr = ""
res += solve(curr)
return res