Almost Even Substrings

Medium

Call a string *almost even* if at most one letter occurs in it an odd number of times. For example, "ddefe" and "gg" are almost even, while "de" is not. Given a string text made of the letters a through j, count how many of its non-empty substrings (contiguous pieces) are almost even. Equal substrings at different positions are counted separately.

Example 1

text="cac" → 4

"c", "a", "c" and the whole "cac" qualify (only "a" is odd there). "ca" and "ac" do not: both letters occur once.

Example 2

text="bbb" → 6

All six substrings use a single letter, so at most that one letter is odd.

Example 3

text="adf" → 3

Constraints

1 ≤ len(text) ≤ 10⁵
text consists of lowercase English letters from a to j

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Hash Table String Prefix Sum

Similar problems

Palindrome After a Few Fixes Medium Even Vowel Stretch Medium Three-Letter Palindromes in a Word Medium Recurring Gene Windows Medium Split Into Equal-XOR Halves Medium

Input

text="cac"

Expected

Run checks the first 3 tests in your browser. Submit checks all 78 tests on the server, hidden ones included.