[Solution] Polycarp Writes a String from Memory solution codeforces

Polycarp Writes a String from Memory solution codeforces – Polycarp has a poor memory. Each day he can remember no more than 33 of different letters.

Table of Contents

[Solution] Polycarp Writes a String from Memory solution codeforces

Polycarp wants to write a non-empty string of 𝑠s consisting of lowercase Latin letters, taking minimum number of days. In how many days will he be able to do it?

Polycarp initially has an empty string and can only add characters to the end of that string.

For example, if Polycarp wants to write the string lollipops, he will do it in 22 days:

  • on the first day Polycarp will memorize the letters loi and write lolli;
  • On the second day Polycarp will remember the letters pos, add pops to the resulting line and get the line lollipops.

If Polycarp wants to write the string stringology, he will do it in 44 days:

  • in the first day will be written part str;
  • on day two will be written part ing;
  • on the third day, part of olog will be written;
  • on the fourth day, part of y will be written.

For a given string 𝑠s, print the minimum number of days it will take Polycarp to write it.

[Solution] Polycarp Writes a String from Memory solution codeforces

The first line of input data contains a single integer 𝑡t (1𝑡1041≤t≤104) — the number of test cases.

Each test case consists of a non-empty string 𝑠s consisting of lowercase Latin letters (the length of the string 𝑠s does not exceed 21052⋅105) — the string Polycarp wants to construct.

It is guaranteed that the sum of string lengths 𝑠s over all test cases does not exceed 21052⋅105.

Output

For each test case, print a single number — minimum number of days it will take Polycarp to write the string 𝑠s from memory.

[Solution] Polycarp Writes a String from Memory solution codeforces

Example
input

Copy
6
lollipops
stringology
abracadabra
codeforces
test
f
output

Copy
2
4
3
4
1
1

 

For Solution

Click Here

Leave a Comment