Hackerrank - String Construction Solution
1 min read

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

Enjoying these posts? Subscribe for more


Adblocker detected! Please consider reading this notice.

We've detected that you are using AdBlock Plus or some other adblocking software which is preventing the page from fully loading.

That's okay. But without advertising-income, we can't keep making this site awesome.

We don't have any banner, Flash, animation, obnoxious sound, or popup ad. We do not implement these annoying types of ads!

We need money to operate the site, and almost all of it comes from our online advertising.

Please add thepoorcoder.com to your ad blocking whitelist or disable your adblocking software.

×