THREE - help in forming testcase which will give WA

help
#1

import java.util.;
import java.lang.;
import java.io.*;

/* 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.

#2

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

#3

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.

#4

What does your code output for
1
aaaabcccc

#5

Ohh I see, it gives 2 but correct answer should be 3. Thanks

1 Like
#6

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.

1 Like
#7

Correct. I did the exact opposite of this lol.

1 Like