As you already know the question String Construction Hackerrank Problem
But let’s understand it in a more simple way.
A girl wants to append/join some string(character, substring) in a string that is suppose ‘p’.
but for every join, it will cost $1, but there are some good things. she can append a substring also if it will match from previous.
this means if she wants to join ‘abcbcabc’
it will cost her $5 only because she will join
a -> $1 result—-a
b -> $1 result—-ab
c -> $1 result—-abc
now she can take ‘bc’ as substring from result ‘abc’
so,
bc -> $1 result—-abcbc
now again she can take ‘abc’ as substring from result ‘abcbc’
so,
abc -> $1 result—-abcbcabc
so cost is $1+1+1+1+1=$5
if you will find a string it will reduce your cost. so help her to minimize the cost and find the cost if you will be given
the resultant string like ‘abcbcabc’
‘
Input condition
The first line contains a single integer, n, denoting the number of strings.
Each line i of the n subsequent lines contains a single string, si.
Limitation
1<=n<=5
1<=m<=105
Subtasks
1<=m<=103 for 45% of the maximum score.
Output condition
For each string (where 0<=i<=n), print the minimum cost of constructing string on a new line.
Input Example
2
abcd
abab
Output Example
4
2
if you want to learn about go to Substring Wikipedia
Solution
#include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while( t-- ) { string s; cin >> s; int M[26] = {0}, ans = 0; for( auto it: s ) { if(!M[it-'a']) { ans ++; } M[it-'a'] = 1; } cout << ans << "\n"; } return 0; }
#include <iostream> #include <algorithm> #include <unordered_map> using namespace std; int main(){ int n; cin >> n; for(int a0 = 0; a0 < n; a0++){ string s; cin >> s; set<char> s1; for(int i=0;i<s.length();i++) s1.insert(s[i]); cout<<s1.size()<<endl; } return 0; }
#!/bin/python
import sys
def ans(s):
return len(set(s))
n = int(raw_input().strip())
for a0 in xrange(n):
s = raw_input().strip()
print ans(s)
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
for(int a0 = 0; a0 < n; a0++){
String s = in.next();
HashSet<Character> set = new HashSet<>();
int cost = 0;
for (int i = 0; i < s.length(); i++) {
if (!set.contains(s.charAt(i))) {
cost++;
set.add(s.charAt(i));
}
}
System.out.println(cost);
}
}
}