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=“ ”.
- Append character ‘a’ to p at a cost of 1 dollar, p= “a”.
- Append character ‘b’ to p at a cost of 1 dollar, p= “ab”.
- Append character ‘c’ to p at a cost of 1 dollar, p= “abc”.
- 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=“ ”.
- Append character ‘a’ to p at a cost of 1 dollar, p= “a”.
- Append character ‘b’ to p at a cost of 1 dollar, p= “ab”.
- 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
- Use Hash Set to store the String Characters.
- Hash Set fetch only non-repeated characters from the string. Because As we know that HashSet not stores duplicate elements.
- 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;}