Number of Wonderful Substrings [a fun variation]

Revision en1, by calmpsychopath, 2024-05-02 00:40:48

Hey guys, I was trying to solve the question 1915. Number of Wonderful Substrings on Leetcode.

Problem Statement

Pretty cool problem. Do give it a go before reading further!

Now, I decided to make the problem a bit more challenging, by slightly changing the statement (and perhaps changing the constraints aswell).

Original Statement: at most one letter appearing odd number of times.
New Statement(s):
1. atmost $$$k$$$ letters appearing odd number of times.
2. atleast $$$k$$$ letters appearing odd number of times.
3. atmost $$$k$$$ letters appearing even number of times.
4. atleast $$$k$$$ letters appearing even number of times.

Here is my Approach for solving $$$[1]$$$

Approach
Implementation within Leetcode (C++)

I've set $$$k = 1$$$ as per the original question, which gives TLE on larger test cases (passing 70/88 testcases).

Thought process for 2, 3 and 4.

A few questions here!

  • Is my thought process/approach correct ?

  • How should I calculate the Time Complexity of the above approach ?.
    I'm confused if precompute function takes $$$O(2^{10})$$$ or $$$O(2^{10}*n)$$$ due to map insertions.
    There are 4 nested for loops for the actual computation. Can I simply say $$$O(n^{4})$$$ as Time Complexity ? How can I improve on this ?

  • Lets say if I change constraints include all characters from $$$a$$$ to $$$z$$$, how would the Time Complexity would be affected ?

Lastly, I would like to know if there are any similar problems that you know of!

Tags bit-masks, prefix-sum, strings, maps

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English calmpsychopath 2024-05-02 00:55:17 0 (published)
en3 English calmpsychopath 2024-05-02 00:53:49 9
en2 English calmpsychopath 2024-05-02 00:45:57 106 Final Touchups - 0
en1 English calmpsychopath 2024-05-02 00:40:48 4908 Initial revision (saved to drafts)