Even Letter Pieces

Medium

Call a string even if every letter it contains occurs the same number of times. For example, "abab" and "xyz" are even, while "aab" is not. A string made of a single letter (repeated or not) is always even. You are given a string text. Cut it into contiguous pieces so that each piece is even. Return the smallest possible number of pieces.

Example 1

text="aabbcab" → 2

For example, "aabb" + "cab": the first piece has two a's and two b's, the second one of each of c, a and b. The whole string fails: three a's and b's but a single c.

Example 2

text="xyzzyx" → 1

Each letter appears exactly twice, so the whole string is one piece.

Example 3

text="aab" → 2

"aab" itself is uneven, but "a" + "ab" works: two pieces.

Constraints

1 ≤ len(text) ≤ 1000
text consists of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Hash Table String Dynamic Programming Counting

Similar problems

The Growing String Medium Length of a Growing Word Hard Make Letter Counts Equal Hard Split Into Dictionary Words Medium A Hint for a Digit Guess Medium

Input

text="aabbcab"

Expected

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