unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 1915: Number of Wonderful Substrings

link

For each substring, we can check if it is wonderful.

Time: \mathcal{O}(n^3), space: \mathcal{O}(n).

class Solution:
    def wonderfulSubstrings(self, word: str) -> int:
        def is_wonderful(word, begin, end):
            char_count = {}
            for i in range(begin, end+1):
                c = word[i]
                char_count[c] = char_count.get(c, 0) + 1
            return sum(count%2 == 1 for _, count in char_count.items()) < 2

        n = len(word)
        wonderful_count = 0
        for begin in range(n):
            for end in range(begin, n):
                wonderful_count += (1 if is_wonderful(word, begin, end) else 0)
        
        return wonderful_count

We can optimize is_wonderful by keeping track of the count of characters that appear odd number of times while building the char_count map.

class Solution:
    def wonderfulSubstrings(self, word: str) -> int:
        def is_wonderful(word, begin, end):
            odd_char_count = 0
            char_count = {}
            for i in range(begin, end+1):
                c = word[i]
                if c not in char_count:
                    char_count[c] = 1
                    odd_char_count += 1
                else:
                    char_count[c] += 1
                    odd_char_count += (1 if char_count[c] % 2 == 1 else -1)
            return odd_char_count < 2

        n = len(word)
        wonderful_count = 0
        for begin in range(n):
            for end in range(begin, n):
                wonderful_count += (1 if is_wonderful(word, begin, end) else 0)
        
        return wonderful_count

Using the same idea for each begin, we can get rid of is_wonderful.

Time: \mathcal{O}(n^2), space: \mathcal{O}(n).

class Solution:
    def wonderfulSubstrings(self, word: str) -> int:
        n = len(word)
        wonderful_count = 0
        for begin in range(n):
            odd_char_count = 0
            char_count = {}
            for end in range(begin, n):
                c = word[end]
                if c not in char_count:
                    char_count[c] = 1
                    odd_char_count += 1
                else:
                    char_count[c] += 1
                    odd_char_count += (1 if char_count[c]%2 == 1 else -1)
                
                wonderful_count += (1 if odd_char_count < 2 else 0)
        
        return wonderful_count

tanvirdotzaman

,

Leave a comment