Demux Problems Submissions Users Contests Log in Sign up


Weird Family Reunion


Submit solution

Points: 100
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
C, C++, Java, Python

In a family reunion, many families were invited.

Let's say n people come to the union. Every family_name can be represented as a English lowercase alphabet.

Example: aba

  • \(1^{st}\) guest is of family a
  • \(2^{nd}\) guest is of family b
  • \(3^{rd}\) guest is of family a

Conditions for sitting arrangements

  • every member of a Family should sit on the same table
  • To avoid conflicts between any two families, you want the number of people sitting on a table as minimum as possible

Table 1 will contain guests from 1 to \(x_1\)

Table 2 will contain guests from \(x_1 + 1\) to \(x_2 \)

Table 3 will contain guests from \(x_2 + 1\) to \(x_3\)

and so on..

You need to find the number of Tables satisfying the conditions, and number of guests on each table.

See Example for more clarification

Input

a string S consisting of lowercase English alphabets

Output

The first line contains an integer n, number of tables The next line contains n space-separated integers, \(g_1, g_2, ..., g_n\) where \(g_i\) represents number of guests on Table \(i\)

Constraints

1 \(\leq\) S.length \(\leq\) 500

Example

Input

abacaddeghe

Output

3
5 2 4

Explanation

Table-1 consists of Family a, b and c

Table-2 consists of Family d

Table-3 consists of Family e, g and h

As we can see all the members of family a are on same table and similarly for all other family as well.

If we keep all guests on same table, condition 1 will satisfy but condition 2 will fail (minimum number of guests on a table)


Comments


  • 0
    Kushal  commented on June 8, 2021, 9:20 p.m.

    I didn't understand the question properly Can anyone explain it to me?