Page Contents
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 English 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 occurrence separately.
A substring is a contiguous sequence of characters in a string.
Example 1:
Input: word = "aba" Output: 4 Explanation: The four wonderful substrings are underlined below: - "aba" -> "a" - "aba" -> "b" - "aba" -> "a" - "aba" -> "aba"
Example 2:
Input: word = "aabb" Output: 9 Explanation: The nine wonderful substrings are underlined below: - "aabb" -> "a" - "aabb" -> "aa" - "aabb" -> "aab" - "aabb" -> "aabb" - "aabb" -> "a" - "aabb" -> "abb" - "aabb" -> "b" - "aabb" -> "bb" - "aabb" -> "b"
Example 3:
Input: word = "he" Output: 2 Explanation: The two wonderful substrings are underlined below: - "he" -> "h" - "he" -> "e"
Constraints:
1 <= word.length <= 105
word
consists of lowercase English letters from'a'
to'j'
.
Program:
class Solution:
# idea: we don't need to know exact substring to define if it's "wonderful" or not
# but rather if number of occurrences of each letter is odd/even;
# so there are only two states for each letter, so we can use binary mask to represent any substring
#
# for example "0101" means represend ("d" even number, "c" - odd, "b" - even, "a" - odd);
#
# we can iterate through word and remember all prefix masks
# + for each new mask find number of previous prefix masks that make substring in between "wonderful"
#
# if (current_mask ^ earlier_mask) == mask_with_0_or_1_bit_set => we have a "wonderful" substring
#
# example: "ccbbc"
# "" - { mask: 000, mask_count: [0, 0, 0, 0, 0, 0, 0, 1] }
# "c" - { mask: 100, mask_count: [0, 0, 0, 1, 0, 0, 0, 1] }
# "cc" - { mask: 000, mask_count: [0, 0, 0, 1, 0, 0, 0, 2] }
# "ccb" - { mask: 010, mask_count: [0, 0, 0, 1, 0, 1, 0, 2] }
# "ccbb" - { mask: 000, mask_count: [0, 0, 0, 1, 0, 1, 0, 3] }
# "ccbbc" - { mask: 100, mask_count: [0, 0, 0, 2, 0, 1, 0, 3] }
#
# what is mask count:
# mask: [111, 110, 101, 100, 011, 010, 001, 000]
# mask_count: [ 0, 0, 0, 2, 0, 1, 0, 3]
# we saw 2 "100" masks, 1 "010" mask and 3 "000" masks
def wonderfulSubstrings(self, word: str) -> int:
mask = 0
mask_count = [0] * 1024
mask_count[mask] += 1
res = 0
for letter in word:
mask ^= 1 << ord(letter) - ord("a")
res += mask_count[mask]
for i in range(10):
res += mask_count[mask ^ 1 << i]
mask_count[mask] += 1
return res
Credit : Here
Weekly Contest 247
- Maximum Product Difference Between Two Pairs
- Cyclically Rotating a Grid
- Number of Wonderful Substrings
- Count Ways to Build Rooms in an Ant Colony
Biweekly Contest 55
- Remove One Element to Make the Array Strictly Increasing
- Remove All Occurrences of a Substring
- Maximum Alternating Subsequence Sum
- Design Movie Rental System
June Long Challenge 2021 Solutions
- Maximum Frequent Subarray Sum solution codechef
- Dual Distance solution codechef
- Optimal Xor Set solution codechef
- Minimum Subtree Cover solution codechef
- Minimum Dual Area solution codechef
- Bitwise Tuples solution codechef
- Shortest Route solution codechef
- Bella ciao solution codechef
- Summer Heat solution codechef
March Long Challenge 2021 Solutions
- An Interesting Sequence ISS SOLUTION
- Tree House THOUSES SOLUTION
- Valid Paths VPATH SOLUTION
- Modular Equation MODEQ SOLUTION
- Tic Tac Toe TCTCTOE SOLUTION
- Xor Equality XOREQUAL SOLUTION
- Golf LKDNGOLF SOLUTION
- Solubility SOLBLTY SOLUTION
April Long Challenge 2021 Solutions
- Chef and Dice SDICE Solution
- Worthy Matrix KAVGMAT Solution
- Binary String MEX MEXSTR Solution
- Boolean Game BOOLGAME Solution
- Tree Permutations TREEPERM Solution
- Destroy the EMP Chip CHAOSEMP Solution
- Chef and Pair Flips PAIRFLIP Solution
- String Power STRPOW Solution
- Brahma and Shiva SHRINES Solution
- Water Sort Puzzle (Challenge) WTRSORT Solution
- World Record BOLT Solution
- Strong Language SSCRIPT Solution
- Valid Pair SOCKS1 Solution
Codechef Long Challenge Solutions
February Long Challenge 2021
- 1. Frog Sort Solution Codechef
- 2. Chef and Meetings Solution Codechef
- 3. Maximise Function Solution Codechef
- 4. Highest Divisor Solution Codechef
- 5. Cut the Cake Challenge Solution Codechef
- 6. Dream and the Multiverse Solution Codechef
- 7. Cell Shell Solution Codechef
- 8. Multiple Games Solution Codechef
- 9. Another Tree with Number Theory Solution Codechef
- 10. XOR Sums Solution Codechef
- 11. Prime Game Solution CodeChef
- 12. Team Name Solution Codechef
January Long Challenge 2021
- Chef and Division 3 DIVTHREE SOLUTION Code Chef
- Encoded String DECODEIT SOLUTION Code Chef
- Point Of Impact BILLRD SOLUTION Code Chef
- Fair Elections FAIRELCT SOLUTION Code Chef
- Watching CPL WIPL SOLUTION Code Chef
- Chef and Ants ANTSCHEF SOLUTION Code Chef
- Blackjack BLKJK SOLUTION Code Chef
- And-Or Game ORAND SOLUTION Code Chef
- Stack-Queue Sort (Challenge) SQSORT SOLUTION Code Chef
- Expected Number of SCCs RCTEXSCC SOLUTION Code Chef
- Curious Matrix CURMAT SOLUTION Code Chef
- Cool Subsets COOLSBST SOLUTION Code Chef
- Sequence Creation ARCRT SOLUTION Code Chef
- Greedy Students GRDSTD SOLUTION Code Chef
November Challenge 2020 SOLUTION CodeChef
- Ada and Dishes SOLUTION ADADISH
- Iron Magnet and Wall SOLUTION FEMA2
- Magical Candy Store SOLUTION CNDYGAME
- Unusual Queries SOLUTION UNSQUERS
- Red-Black Boolean Expression SOLUTION RB2CNF
- Chef and the Combination Lock SOLUTION CHEFSSM
- Scalar Product Tree SOLUTION SCALSUM
- Connect on a Grid (Challenge) SOLUTION CONGRID
October Lunchtime 2020 CodeChef SOLUTIONS
- AND Plus OR SOLUTION ANDOR
- Chef and Subtree MEXs SOLUTION SUBMEXS
- Chef Likes Good Sequences SOLUTION GSUB
- Cute Chef Gift SOLUTION COPAR
- Chef Is Just Throwing Random Words SOLUTION SSO
- Counting Spaghetti SOLUTION CDSUMS
- Chef and Edge Flipping SOLUTION EFLIP
Related :
- A. Shandom Ruffle SOLUTION
- B. Pear TreaP SOLUTION
- C. Sneetches and Speeches 3 SOLUTION
- D. The Grim Treaper SOLUTION
- Y. Sneetches and Speeches 1 SOLUTION
- Z. Trick or Treap SOLUTION
- A. Floor Number SOLUTION CODE FORCES
- B. Symmetric Matrix SOLUTION CODE FORCES
- C. Increase and Copy SOLUTION CODE FORCES
- D. Non-zero Segments SOLUTION CODE FORCES
- E. Rock, Paper, Scissors SOLUTION CODE FORCES
- F. Number of Subsequences SOLUTION CODE FORCES
Related :
- Chef and Easy Queries SOLUTIONS CHEFEZQ
- Covid Run SOLUTIONS CVDRUN OCTOBER CHALLENGE
- Positive AND SOLUTIONS POSAND
- Replace for X SOLUTIONS REPLESX
- Village Road Network SOLUTIONS VILLNET
- Random Knapsack SOLUTIONS RANDKNAP
- D-Dimensional MST SOLUTIONS DDIMMST
- Compress all Subsegments SOLUTIONS SEGCOMPR
- Adding Squares SOLUTIONS ADDSQURE
- Inversions SOLUTIONS INVSMOD2 OCOTBER CHALLENGE
- Rooted Minimum Spanning Tree SOLUTIONS ROOTMST