Amazon Online Assessment (OA) - Find Substrings

Given a string S of lowercase letters.

You need to find as many substrings from S that meet the following conditions.

1. No overlap among substrings.
2. One letter can only exist in one substring. For every letter C in a substring, all occurrences of the letter C must also be in that substring.
3. You want to find as many substrings as possible.
4. If there are two solutions with the same number of substrings, return the one with the smaller total length.

Input

The input consists of one argument:

S: a string of lowercase letters

Output

Return substrings as a list.

Examples

Example 1:

Input:

S = "baddacxb"

Output: ["bb", "a", "c", "x"]

Example 2:

Input:

S = "bbeadcxede"

Output: ["dd", "c", "x"]

Explanation:

Here, ["adda", "c", "x"] is not considered a correct answer. Because the total length of ["dd","c", "x"] is 4, which is smaller than the total length of ["adda", "c", "x"], which is 6.

Try it yourself