String Construction Hacker Rank Solution by Java

Amanda has a string, , of  lowercase letters that she wants to copy into a new string, . She can perform the following operations any number of times to construct 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 (i.e., ), find and print the minimum cost of copying each  to  on a new line.

Input Format

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

Constraints

Subtasks

•  for  of the maximum score.

Output Format

For each string  (where ), print the minimum cost of constructing 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 "".

Java Code:

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    static int stringConstruction(String s) {
        // Complete this function
        ArrayList<Character> p = new ArrayList<>();
        char[] chs = s.toCharArray();
        p.add(chs[0]);
        int i =1;
        int charges = 1;
        while(i<s.length())
        {
            if(p.contains(chs[i]))
            {
                
                i++;
            }
            else
            {
                p.add(chs[i]);
                charges++;
                i++;
            }
        }
        return charges;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int q = in.nextInt();
        for(int a0 = 0; a0 < q; a0++){
            String s = in.next();
            int result = stringConstruction(s);
            System.out.println(result);
        }
        in.close();
    }
}