This is my fifth day of the November Gwen Challenge. Check out the final Gwen Challenge 2021 for more details

link

Leetcode-cn.com/contest/wee…

There are four questions in the weekly competition. Today, I will bring you the explanation of the first two questions.

The title

5918. Count the vowel substring in the string

Split + double pointer

parsing

A traversal separates the fragments that meet the partial requirements, and then calculates the substring for each fragment. Double pointer method is used to calculate each fragment, that is, double pointer left and right are used to traverse right from left=0. VowelCountDict (defaultdict is the most convenient in Python) is used to record the number of vowels. Use the zeroCount variable to record vowels that have not yet occurred (zeroCoun-1 when the letter count changes from 0 to 1). When zeroCount is 0, the distance between the right pointer and the end of the vowel fragment is calculated, which is the number of eligible substrings starting with left. Then left+=1, determine whether the right position is valid (vowelCountDict has items that change from 1 to 0) and update the right position, adding the new number of substrings; Note that in the inner loop you also need to determine if the right position is past the end.

code

My solution

class Solution:
    def countVowelSubstrings(self, word: str) - >int:
        vowels = ['a'.'e'.'i'.'o'.'u']
        p = 0
        self.vowelStrCount, self.word = 0, word
        while p < len(word):
            if word[p] in vowels:
                nextP = p + 1
                while nextP < len(word) and word[nextP] in vowels:
                    nextP += 1
                if nextP - p >= 5:
                    self.queryVowelStrs(p, nextP)
                p = nextP + 1
            else:
                p += 1
        return self.vowelStrCount
    
    def queryVowelStrs(self, p, nextP) :
        vowelCount = defaultdict(int)
        zeroCount = 5
        left, right = p, p
        while right < nextP:
            while right < nextP and zeroCount > 0:
                vowelCount[self.word[right]] += 1
                if vowelCount[self.word[right]] == 1:
                    zeroCount -= 1
                right += 1
            ifzeroCount ! =0:
                break
            while zeroCount == 0:
                self.vowelStrCount += nextP - right + 1
                vowelCount[self.word[left]] -= 1
                if vowelCount[self.word[left]] == 0:
                    zeroCount += 1
                left += 1
        return
Copy the code

More concise split + double pointer

parsing

Same idea. Strings. FieldsFunc of Go and Strings. ContainsRune can easily separate the required fragments in string, and then also double pointer + array used as dictionary to implement O(n) traversal of the string. The difference is that the perspective of counting the number of strings that meet the requirement is the maximum number of places that the left pointer can go from each right pointer, that is, the number of places that the fragment can start to the left pointer can be added.

code

(reprinted from lingchashan Ai Fu’s solution)

func countVowelSubstrings(word string) (ans int) {
	for _, s := range strings.FieldsFunc(word, func(r rune) bool { return! strings.ContainsRune("aeiou", r) }) { // Split out the string containing only vowels
		cnt := ['v']int{}
		l := 0
		for _, ch := range s {
			cnt[ch]++
			for cnt[s[l]] > 1 { // Move the left pointer only if there is more than one vowel
				cnt[s[l]]--
				l++
			}
			if cnt['a'] > 0 && cnt['e'] > 0 && cnt['i'] > 0 && cnt['o'] > 0 && cnt['u'] > 0 { // Must contain all five vowels
				ans += l + 1}}}return
}
Copy the code

Another violent solution

The other solutions are basically O(n^2) substring traversal with two variables. In traversal, you can use the dictionary to determine the number of vowels and break them when you encounter a non-vowel (see this answer). It is also possible to use Python’s native set to determine if only vowels are met (see here), but this is more complex than O(n^2) (not sure if it is O(n^3), due to the complexity of retrieving a string set in Python).

5919. Vowels in all substrings

A time-out solution

Train of thought

For each position of a character, if it is a vowel character, determine how many times it will appear in a substring of each length based on its position: min(n-j, I), the right-most position at the beginning of a substring of that length, minus Max (0, i-j+1), the left-most position that can appear. But because the data is 10 to the fifth and it takes order n^2 to iterate over every position and length, it’s going to time out.

code

class Solution:
    def countVowels(self, word: str) - >int:
        n, ans = len(word), 0
        for i in range(0, n):
            if word[i] in ['a'.'e'.'i'.'o'.'u'] :for j in range(1, n+1):
                    ans += min(n-j, i) - max(0, i-j+1) + 1
        return ans
Copy the code

Multiplication optimizes addition of O(n)

parsing

Replace the above traversal plus each length with a multiplication: Consider all contain word word [r] l… [I], if and only if 0 < = I < = l and I < = r < = len (word) – 1, so including word word [r] l… [I] have (I + 1) * (len (word) – I), I can solve it in order n.

code

class Solution:
    def countVowels(self, word: str) - >int:
        n, ans = len(word), 0
        for i in range(0, n):
            if word[i] in ['a'.'e'.'i'.'o'.'u']:
                ans += (i+1) * (n-i)
        return ans
Copy the code

Based on DP

parsing

For all I +1 substrings ending in word[I], word[I] without a vowel has the same number of vowels as all I substrings ending in word[i-1]. For word[I] without a vowel, word[I] has an extra vowel in all I +1 substrings. So setting a prev variable that represents the number of vowels in the substring ending in Word [i-1] and then iterating through the string updating its value as appropriate, and finding the sum of preVs at all positions is the result.

code

class Solution:
    def countVowels(self, word: str) - >int:
        n, prev, ans = len(word), 0.0
        for i in range(0, n):
            if word[i] in ['a'.'e'.'i'.'o'.'u']:
                prev += i+1
            ans += prev
        return ans
Copy the code