周赛 Weekly Contest 417

3304. Find the K-th Character in String Game I

class Solution:
    def kthCharacter(self, k: int) -> str:
        res = "a"
        while len(res) < k:
            for c in res:
                if c == "z":
                    res += "a"
                else:
                    res += chr(ord(c)+1)
        return res[k-1]
                

3305. Count of Substrings Containing Every Vowel and K Consonants I

class Solution:
    def countOfSubstrings(self, word: str, k: int) -> int:
        d = dict()
        for c in "aeiou":
            d[c] = 0
        cntV = 0
        cntC = 0
        i = 0
        j = 0
        ans = 0

        while j < len(word):
            c = word[j]
            if c in "aeiou":
                if d[c] == 0:
                    cntV += 1
                d[c] += 1
            else:
                cntC += 1
            
            while i < j and cntC > k:
                c = word[i]
                if c in "aeiou":
                    d[c] -= 1
                    if d[c] == 0:
                        cntV -= 1
                else:
                    cntC -= 1
                i+=1

            i2 = i
            cntV2 = cntV
            cntC2 = cntC
            d2 = copy.copy(d)
            while i2 < j and cntV2 == 5 and cntC2 == k:
                c = word[i2]
                if c in "aeiou":
                    d2[c] -= 1
                    if d2[c] == 0:
                        cntV2 -= 1
                else:
                    cntC2 -= 1
                i2 += 1
                ans += 1
            j+=1
        return ans

3306. Count of Substrings Containing Every Vowel and K Consonants II

class Solution:
    def countOfSubstrings(self, word: str, k: int) -> int:
        d = dict()
        for c in "aeiou":
            d[c] = 0
        cntV = 0
        cntC = 0
        i = 0
        j = 0
        ans = 0


        while j < len(word):
            c = word[j]
            if c in "aeiou":
                if d[c] == 0:
                    cntV += 1
                d[c] += 1
            else:
                cntC += 1
            
            while i < j and cntC > k:
                c = word[i]
                if c in "aeiou":
                    d[c] -= 1
                    if d[c] == 0:
                        cntV -= 1
                else:
                    cntC -= 1
                i+=1


            if cntV == 5 and cntC == k:
                i2 = i
                cntV2 = cntV
                cntC2 = cntC
                d2 = copy.copy(d)
                curN = 0
                while i2 < j and cntV2 == 5 and cntC2 == k:
                    c = word[i2]
                    if c in "aeiou":
                        d2[c] -= 1
                        if d2[c] == 0:
                            cntV2 -= 1
                    else:
                        cntC2 -= 1
                    i2 += 1
                    curN += 1
                    ans += 1
                while j+1 < len(word) and word[j+1] in "aeiou":
                    j += 1
                    c = word[j]
                    d[c] += 1

                    if d2[c] == 0:
                        cntV2 += 1
                    d2[c] += 1
                    if cntV2 == 5:
                        while i2 < j and cntV2 == 5 and cntC2 == k:
                            c = word[i2]
                            if c in "aeiou":
                                d2[c] -= 1
                                if d2[c] == 0:
                                    cntV2 -= 1
                            else:
                                cntC2 -= 1
                            i2 += 1
                            curN += 1
                    ans += curN
            j+=1
        return ans

3307. Find the K-th Character in String Game II

class Solution:
    def kthCharacter(self, k: int, operations: List[int]) -> str:
        i = len(operations)

        def dfs(k, i):
            if k == 1:
                return "a"
            while i > 0 and not(k <= 2**i and k > 2**(i-1)):
                i -= 1
            nextK = k - 2**(i-1) #2
            # print(i, nextK)
            if operations[i-1] == 0:
                return dfs(nextK, i-1)
            else:
                c = dfs(nextK, i-1)
                if c == "z": 
                    return "a"
                else: 
                    return chr(ord(c)+1)
        return dfs(k, i)