Hey guys, I was trying to solve the question 1915. Number of Wonderful Substrings on Leetcode.
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]$$$
I've set $$$k = 1$$$ as per the original question, which gives TLE on larger test cases (passing 70/88 testcases).
A few questions here!
Is my thought process/approach correct ? How can I improve on this ?
How should I calculate the Time Complexity of the above approach ?.
I'm confused ifprecompute
function takes $$$O(2^{10})$$$ or $$$O(2^{10}*n)$$$ due to map insertions.
There are 4 nested for loops for the actual computation in my code. Can I simply say $$$O(n^{4})$$$ as Time Complexity ?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!