You've successfully subscribed to The Poor Coder | Hackerrank Solutions
Great! Next, complete checkout for full access to The Poor Coder | Hackerrank Solutions
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Hackerrank - String Construction Solution

Hackerrank - String Construction Solution

Beeze Aal
Beeze Aal

Amanda has a string of lowercase letters that she wants to copy to a new string. She can perform the following operations with the given costs. She can perform them any number of times to construct a new string :

  • Append a character to the end of string ¬†at a cost of ¬†dollar.
  • Choose any substring of ¬†and append it to the end of ¬†at no charge.

Given  strings , find and print the minimum cost of copying each  to  on a new line.

For example, given a string , it can be copied for  dollars. Start by copying ,  and  individually at a cost of  dollar per character. String  at this time. Copy  to the end of  at no cost to complete the copy.

Function Description

Complete the stringConstruction function in the editor below. It should return the minimum cost of copying a string.

stringConstruction has the following parameter(s):

  • s: a string

Input Format

The first line contains a single integer , the number of strings.
Each of the next  lines contains a single string, .

Constraints

Subtasks

  • for ¬†of the maximum score.

Output Format

For each string  print the minimum cost of constructing a new string  on a new line.

Sample Input

2
abcd
abab

Sample Output

4
2

Explanation

Query 0: We start with  and .

  1. Append character '' to  at a cost of  dollar, .
  2. Append character '' to  at a cost of  dollar, .
  3. Append character '' to  at a cost of  dollar, .
  4. Append character '' to  at a cost of  dollar, .

Because the total cost of all operations is  dollars, we print  on a new line.

Query 1: We start with  and .

  1. Append character '' to  at a cost of  dollar, .
  2. Append character '' to  at a cost of  dollar, .
  3. Append substring  to  at no cost, .

Because the total cost of all operations is  dollars, we print  on a new line.

Note

A substring of a string  is another string  that occurs "in"  (Wikipedia). For example, the substrings of the string "" are "", "" ,"", "", "", and "".

Solution in Python

def stringConstruction(s):
    return len(set(s))

for _ in range(int(input())):
    print(stringConstruction(input()))