Pieces Without Shared Letters

Medium

You are given a string text of lowercase English letters. Cut it into consecutive pieces so that every letter occurs in at most one piece: all occurrences of a letter must end up in the same piece. Make as many pieces as possible. Joined in order, the pieces give back the original string. Return the list of piece lengths from left to right.

Example 1

text="abacdcdefe" → [3, 4, 3]

The pieces are "aba", "cdcd" and "efe": each letter lives in one piece only. No finer cut works: cutting off "ab", for instance, would separate the two a's.

Example 2

text="xyzzx" → [5]

The letter x appears at both ends, so the whole string is a single piece.

Example 3

text="qrs" → [1, 1, 1]

Constraints

1 ≤ len(text) ≤ 10⁵
text consists of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Hash Table Two Pointers String

Similar problems

A Subsequence of One Word Only Medium Hidden Anagram Medium No Twin Letters Side by Side Medium Word Growth Chain Medium A Note From Headline Cutouts Medium

Input

text="abacdcdefe"

Expected

[3, 4, 3]

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