1915. Number of Wonderful Substrings

1915. Number of Wonderful Substrings

Medium

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'.

Solution:

class Solution {

    /**
     * @param String $word
     * @return Integer
     */
    function wonderfulSubstrings($word) {
        $ans = 0;
        $prefix = 0;
        $count = array_fill(0, 1024, 0);
        $count[0] = 1;

        foreach(str_split($word) as $c) {
            $prefix ^= 1 << ord($c) - ord('a');
            $ans += $count[$prefix];
            for ($i = 0; $i < 10; ++$i)
                $ans += $count[$prefix ^ 1 << $i];
            ++$count[$prefix];
        }

        return $ans;
    }
}

Contact Links

• LinkedIn
• GitHub