diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /num_wonderful_substr.py | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'num_wonderful_substr.py')
-rw-r--r-- | num_wonderful_substr.py | 34 |
1 files changed, 34 insertions, 0 deletions
diff --git a/num_wonderful_substr.py b/num_wonderful_substr.py new file mode 100644 index 0000000..f4dd059 --- /dev/null +++ b/num_wonderful_substr.py @@ -0,0 +1,34 @@ +# 1915. Number of Wonderful Substrings + +""" +a wonderful string is a string where at most one letter appears an odd number +of times. for example "ccjjc" and "abab" are wonderful, but "ab" is not. +given a string 'word' that consists of the first ten lowercase letters ('a' +through 'j') return the number of wonderful non-empty substrings in 'word'. +if the same substring appears multiple times in 'word', then count each +occurence separately. a substring is a contiguous sequence of character in a +string. +""" + + +class Solution(object): + def wonderfulSubstrings(self, word): + """ + :type word: str + :rtype: int + """ + cnt = [1] + [0] * 1024 + ans, curr = 0,0 + for c in word: + curr ^= 1 << (ord(c) - ord('a')) + ans += cnt[curr] + ans += sum(cnt[curr ^ (1 << i)] for i in range(10)) + cnt[curr] += 1 + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.wonderfulSubstrings("aba")) # expect: 4 + print(obj.wonderfulSubstrings("aabb")) # expect: 9 + print(obj.wonderfulSubstrings("he")) # expect: 2 |