Scale Engineer

Number of Wonderful Substrings

Med
#1748Time: O(n^2 * k), where n is the length of the string and k is the number of distinct characters (10). We have two nested loops to generate O(n^2) substrings. Inside the inner loop, we check the frequency array of size k. Since k is constant, the complexity is effectively O(n^2).Space: O(k), where k is the number of distinct characters (10). This is because we only need a small, constant-size array to store character frequencies for each substring. Thus, the space complexity is O(1).1 company
Patterns
Bit ManipulationPrefix Sum
Data structures
Hash TableString
Companies
DE Shaw

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves generating every possible substring of the input word and then checking each one to see if it qualifies as a 'wonderful' string. A string is wonderful if at most one of its characters appears an odd number of times. While straightforward, this method is computationally expensive.

Algorithm

  • Initialize wonderful_count = 0.
  • Iterate i from 0 to word.length() - 1 (start of substring).
    • Initialize a frequency array freq of size 10 to all zeros.
    • Iterate j from i to word.length() - 1 (end of substring).
      • Update the frequency of word.charAt(j) in freq.
      • Count the number of characters with odd frequencies in freq.
      • If the odd count is less than or equal to 1, increment wonderful_count.
  • Return wonderful_count.

Walkthrough

We use two nested loops to define all substrings. The outer loop sets the starting index i, and the inner loop sets the ending index j. For each substring starting at i, we maintain a frequency map (an array of size 10 for characters 'a' through 'j'). As we extend the substring by incrementing j, we update the character counts. After each character is added, we scan the frequency map to count how many characters have appeared an odd number of times. If this count is 0 or 1, we've found a wonderful substring and increment our total counter.

class Solution {    public long wonderfulSubstrings(String word) {        long count = 0;        int n = word.length();        for (int i = 0; i < n; i++) {            int[] freq = new int[10];            for (int j = i; j < n; j++) {                freq[word.charAt(j) - 'a']++;                int oddCount = 0;                for (int k = 0; k < 10; k++) {                    if (freq[k] % 2 != 0) {                        oddCount++;                    }                }                if (oddCount <= 1) {                    count++;                }            }        }        return count;    }}

Complexity

Time

O(n^2 * k), where n is the length of the string and k is the number of distinct characters (10). We have two nested loops to generate O(n^2) substrings. Inside the inner loop, we check the frequency array of size k. Since k is constant, the complexity is effectively O(n^2).

Space

O(k), where k is the number of distinct characters (10). This is because we only need a small, constant-size array to store character frequencies for each substring. Thus, the space complexity is O(1).

Trade-offs

Pros

  • Simple to understand and implement.

  • Directly follows the problem definition without complex data structures or algorithms.

Cons

  • Highly inefficient due to its O(n^2) time complexity.

  • Will result in a 'Time Limit Exceeded' (TLE) error for large inputs as specified in the problem constraints.

Solutions

class Solution {public  long wonderfulSubstrings(String word) {    int[] cnt = new int[1 << 10];    cnt[0] = 1;    long ans = 0;    int st = 0;    for (char c : word.toCharArray()) {      st ^= 1 << (c - 'a');      ans += cnt[st];      for (int i = 0; i < 10; ++i) {        ans += cnt[st ^ (1 << i)];      }      ++cnt[st];    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem