/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine().trim());
while(t-- > 0) {
String s = br.readLine().trim();
int[] arr = new int[26];
for(int i=0; i<s.length(); i++) {
arr[s.charAt(i)-‘a’]++;
}
long res = 0;
long ones = 0;
long twos = 0;
for(int i=0; i<26; i++) {
res += (arr[i] / 3);
if(arr[i] % 3 == 1) {
ones++;
}
else if(arr[i] % 3 == 2) {
twos++;
}
}
System.out.println(res + Math.min(ones, twos));
}
}
}
What’s wrong with the above logic? I am selecting 3 letters of the same alphabet as pair and keeping count of the remaining ones and twos to form pairs with each other.
Please provide any test case where this code fails, it’s not getting AC even in subtask 1.
For palindrome we just need 2 same characters
And we can put any character in between soo the ans would be
Traversing through arr[26] {
count_pair += arr[i]/2:
}
if count_pair > n/3
Print n/3
else
Print count_pair
Why n/3?
because we can’t insert the remaining character in each pair then
For ex n== 9
Max we can have 3 palindromes(count_pair=3)
If the count_pair is > 3 let’s say it’s 4 then the remaining characters would be 9-4*2= 1
Which won’t fill in all pairs
Yeah, I understood the method you mentioned after reading the editorial. My question was that where would my code fail. An example string would be super helpful.
Try forming all possible 2-1 char pairs first and when you can’t form any 2-1 pair only then try forming word having all characters same. This leads towards an optimal answer.