We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Strings
  4. String Construction

String Construction

Problem
Submissions
Leaderboard
Discussions
Editorial

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 "".

Author

ma5termind

Difficulty

Easy

Max Score

25

Submitted By

66203

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy