String Construction(HackerRank)

QUESTION

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 p:

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

Your task is to find their only non-repeated characters count from String. If a character is repeated don't count that character for 1 dollar.

Sample Input:

2
abcd
abab

Sample Output:

4
2

Explanation:

Query 0: We start with s=“abcd” and p=“ ”.

1. Append character ‘a’ to p at a cost of 1 dollar, p= “a”.
2. Append character ‘b’ to p at a cost of 1 dollar, p= “ab”.
3. Append character ‘c’ to p at a cost of 1 dollar, p= “abc”.
4. Append character ‘d’ to p at a cost of 1 dollar, p= “abcd”.

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

Query 1: We start with s=“abab” and p=“ ”.

1. Append character ‘a’ to p at a cost of 1 dollar, p= “a”.
2. Append character ‘b’ to p at a cost of 1 dollar, p= “ab”.
3. Append character ‘ab’ to p at no cost, p= “abab”.

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

SOLUTION

Java

1. Use Hash Set to store the String Characters.
2. Hash Set fetch only non-repeated characters from the string. Because As we know that HashSet not stores duplicate elements.
3. Count only those non-repeated characters.

static int stringConstruction(String s) {
int count = 0;
HashSet<Character> String_s1 = new HashSet<>();
for (int i = 0; i < s.length(); i++) {
String_s1.add(s.charAt(i));
}
count = String_s1.size();
return count;
}