Self-Contained Pieces of a String

Hard

Call a non-empty substring (contiguous piece) of text **closed** if, for every letter it contains, all other occurrences of that letter in text are inside it too. Choose as many non-overlapping closed substrings as possible. If several choices reach that count, take the one with the smallest total length; it is always unique. Return the chosen substrings in any order.

Example 1

text="xyxzwwz" → ['y', 'ww']

The closed pieces are "xyx", "y", "zwwz", "ww" and the whole string. Taking "y" and "ww" gives two disjoint pieces with the smallest total length.

Example 2

text="abab" → ['abab']

Any piece with an a must also take both bs, so the only closed piece is the whole string.

Example 3

text="qrrsq" → ['rr', 's']

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 String

Similar problems

Does the Text Fit the Pattern Hard Equal Letters Kept Apart Hard Harden the Password Hard Distinct Word Shorthands Hard Mirror Chunk Split Hard

Input

text="xyxzwwz"

Expected

['y', 'ww']

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