Check Algorithm Solution

Problem

Read problem statements in Hindi,Bengali, Mandarin Chinese, Russian, and Vietnamese as well.

One day, Saeed was teaching a string compression algorithm. This algorithm finds all maximal substrings which contains only one character repeated one or more times (a substring is maximal if it we cannot add one character to its left or right without breaking this property) and replaces each such substring by the string "cK", where $K$ is the length of the substring and $c$ is the only character it contains. For example, "aabaaa" is compressed to "a2b1a3".

Saeed wanted to check if the students understood the algorithm, so he wrote a string $S$ on the board and asked the students if the algorithm is effective on $S$, i.e. if the string created by compressing $S$ is strictly shorter than $S$. Help them answer this question.

Input

• The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
• The first and only line of each test case contains a single string $S$.

Output

For each test case, print a single line containing the string "YES" if the algorithm is effective on $S$ or "NO" if it is not.

Constraints

• $1 \le T \le 100$
• $1 \le |S| \le 10^3$
• $S$ may consist of only lowercase English letters.

Subtasks

Subtask #1 (100 points): original constraints

Sample 1:

Input

Output

3
bbbbbbbbbbaa
c
aaaaaaaaaabcdefgh

YES
NO
NO

Explanation:

Example case 1:

• The compressed string of "bbbbbbbbbbaa" is "b10a2", which is shorter.
• The compressed string of "c" is "c1", which is not shorter than "c".
• The compressed string of "aaaaaaaaaabcdefgh" is "a10b1c1d1e1f1g1h1", which is not shorter than "aaaaaaaaaabcdefgh" (both strings have length $17$).

Program :

/* package codechef; // don't place package name! */

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)

{

Scanner sr=new Scanner(System.in);

int t=sr.nextInt();

while(t-->0)

{

   String s=sr.next();

   int p=0,r=1;

   int l=s.length();

   for(int k=1;k<=l;k++)

   {

      if(k==l||s.charAt(k)!=s.charAt(k-1))

      {

       if(r<10)

       p=p+2;

       else if(r<100)

       p=p+3;

       else if(r<1000)

       p=p+4;

       else 

       p=p+5;

       r=1;

      }

      else

       ++r;

   }

  if(p>=l)

  System.out.println("NO");

  else 

  System.out.println("YES");

}

}

}