Leetcode 1915: Number of Wonderful Substrings

Input: The input consists of a string word containing lowercase English letters from 'a' to 'j'.

Example: word = 'abcab'

Constraints:

• 1 <= word.length <= 10^5

• word consists of lowercase English letters from 'a' to 'j'.

Output: Return the number of wonderful non-empty substrings in the word.

Example: 7

Constraints:

Goal: Find all wonderful substrings by checking each substring and counting the ones where at most one letter appears an odd number of times.

Steps:

• Iterate through all possible substrings of the string.

• For each substring, count the frequency of each character.

• Check if the substring is wonderful by ensuring at most one character appears an odd number of times.

Goal: Ensure that the solution works efficiently for large strings.

Steps:

• The length of the word will be at most 10^5.

• The string consists only of the lowercase letters 'a' through 'j'.

Assumptions:

• The string contains only lowercase English letters from 'a' to 'j'.

• The problem will not test empty strings.

• Input: word = 'abcab'

• Explanation: In the word 'abcab', we find 7 wonderful substrings: 'a', 'b', 'c', 'a', 'b', 'ab', 'c'.

Approach: To solve the problem efficiently, we need to iterate through all substrings and count how many of them are wonderful. We can use bitwise operations to track the odd/even frequency of letters.

Observations:

• The input string is constrained to only 'a' through 'j', which limits the number of possible characters in any given substring.

• Checking each substring individually would take too long for large inputs.

• Using a bitmask to track the odd/even frequency of characters can speed up the solution.

Steps:

• Iterate through the string and for each character, update a bitmask that tracks which characters have odd counts.

• Count how many substrings with each bitmask have at most one odd character by leveraging previously seen bitmasks.

Empty Inputs:

• The input will never be empty based on problem constraints.

Large Inputs:

• The algorithm must efficiently handle strings with lengths up to 10^5.

Special Values:

• If the string contains only one character, it will always have one wonderful substring.

Constraints:

• The string length will always be at least 1.

long long wonderfulSubstrings(string word) {
    map<int, int> mp;
    mp[0] = 1;
    int msk = 0;
    long long ans = 0;
    for(int i = 0; i < word.size(); i++) {
        
        int idx = word[i] - 'a';
        msk ^= (1 << idx);
        ans += mp[msk];
        for(int j = 0; j < 10; j++) {
            int lf = msk ^ (1 << j);
            ans += mp[lf];
            }
        mp[msk]++;
        }
    
    return ans;
}

1 : Function Definition

long long wonderfulSubstrings(string word) {

Defines the function 'wonderfulSubstrings' which takes a string 'word' and returns a long long integer representing the number of wonderful substrings.

2 : Variable Initialization

    map<int, int> mp;

Initializes a map 'mp' which keeps track of the frequency of bitmask states encountered during iteration.

3 : Variable Assignment

    mp[0] = 1;

Sets the initial condition where the bitmask value 0 (representing an empty set of characters) is encountered once.

4 : Variable Initialization

    int msk = 0;

Initializes the bitmask 'msk' to 0, which will be used to track the parity of characters in the substring.

5 : Variable Initialization

    long long ans = 0;

Initializes the variable 'ans' to store the total count of wonderful substrings.

6 : Loop Start

    for(int i = 0; i < word.size(); i++) {

Begins a loop to iterate through each character of the word.

7 : Bitmask Update

        int idx = word[i] - 'a';

Calculates the index corresponding to the character in 'word' by subtracting 'a' from the character's ASCII value.

8 : Bitmask Update

        msk ^= (1 << idx);

Updates the bitmask by flipping the bit corresponding to the current character.

9 : Count Update

        ans += mp[msk];

Adds the count of substrings with the current bitmask to the total count of wonderful substrings.

10 : Inner Loop

        for(int j = 0; j < 10; j++) {

Begins a loop to check all possible bitmasks that differ by one bit from the current bitmask.

11 : Bitmask Update

            int lf = msk ^ (1 << j);

Calculates a new bitmask 'lf' by flipping one bit of the current bitmask 'msk'.

12 : Count Update

            ans += mp[lf];

Adds the count of substrings with the modified bitmask 'lf' to the total count of wonderful substrings.

13 : Map Update

        mp[msk]++;

Increments the count of the current bitmask 'msk' in the map 'mp'.

14 : Return Statement

    return ans;

Returns the total count of wonderful substrings.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: We iterate through the string once and keep track of bitmasks using a map for efficient look-up and updates.

Best Case: O(n)

Worst Case: O(n)

Description: We use a map to store bitmasks, and the space complexity depends on the length of the string.

Leetcode 1915: Number of Wonderful Substrings

Explore →