Hackerrank - String Construction Solution

Hackerrank - String Construction Solution

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()))

Subscribe to The Poor Coder | Algorithm Solutions

Don’t miss out on the latest issues. Sign up now to get access to the library of members-only issues.
[email protected]
Subscribe