Hey guys, I was trying to solve the question 1915. Number of Wonderful Substrings on Leetcode.
Problem StatementA 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.
Constraints:
- $$$1 \le word.length \le 10^{5}$$$
- $$$word$$$ consists of lowercase English letters from '$$$a$$$' to '$$$j$$$'.
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]$$$
Implementation within Leetcode (C++)class Solution {
using i64 = long long;
private:
int sum, k;
i64 cnt;
std::array<int, (1 << 10)> freq;
std::unordered_map<int, std::vector<int>> ump;
void precompute() {
for(int i = (1 << 10) - 1; i >= 0; i--) {
int j = __builtin_popcount(i);
ump[j].push_back(i);
}
std::fill(freq.begin(), freq.end(), 0);
}
void compute(int p) {
int csum = __builtin_popcount(sum);
for(int i = csum - p; i <= csum + p; i++) {
for(int j = 0; j < ump[i].size(); j++) {
int z = sum ^ ump[i][j];
cnt += (__builtin_popcount(z) == p)? freq[ump[i][j]]: 0;
}
}
}
public:
i64 wonderfulSubstrings(std::string word) {
precompute();
sum = 0; cnt = 0; k = 1; freq[0] = 1;
for(const char& ch: word) {
int bit = ch - 'a';
sum ^= (1 << bit);
for(int i = 0; i <= k; i++) {
compute(i);
}
++freq[sum];
}
return cnt;
}
};
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. - For calculating the atleast $$$k$$$ variant, we can calculate for atmost $$$k-1$$$ and then subtract it from $$$n*(n+1)/2$$$, $$$n$$$ being the size of the string $$$word$$$.
- For calculating the even variant, we need to keep track of the unset bits, instead of the set bits, followed by the same logic.
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 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 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!