ABABAABA

Description:

You are given a uniformly randomly generated string S, consisting of letters from the set {""A"", ""B""}. Your task is to find a string T that appears in S as a subsequence exactly twice. In other words, you need to find such a string T, that there exist exactly two sets of indexes i1, i2, ..., i|T| and j1, j2, ..., j|T| such that there exists some k, where ik jk and S{i1...i|T|} = S{j1...j|T|} = T. Input The first line of the input contains an 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. The string S was generated randomly. For a generating string S, we first choose an integer N denoting a length of S. After that every symbol of the string S is chosen randomly from the set {""A"", ""B""} and the both symbols have equal probability to be chosen. Note that N is not choosen randomly. Output For each test case, output a string that occurs exactly twice as a subsequence in S, or output -1 if there is no such string. If there are more than one possible subsequences occurring exactly two times, you can print any one of them. Constraints 1 <=T<= 10 Explanation Test case #1: The string ""AAAA"" appears once as a subsequence in itself. The string ""AAA"" appears four times as a subsequence in ""AAAA""; possible positions: {2, 3, 4}, {1, 3, 4}, {1, 2, 4}, {1, 2, 3}. The strings ""AA"" and ""A"" also appear in ""AAAA"" as a subsequence strictly more than twice. So, there is no string of ""AAAA"", which appears exactly twice. Hence answer is -1. Test case #2: Two occurrences of ""B"" in ""BAB"" are {1} and {3} (1-based indexing)." Test Case 1 Input (stdin) 2 AAAA BAB Expected Output -1 B Test Case 2 Input (stdin) 3 AAAAA BABBA AAA Expected Output -1 A -1

Program :

  • #include <stdlib.h>
    #include<stdio.h>
    #include<string.h>
    #include<math.h>
    int main()
    {int t;
     scanf("%d",&t);
     while(t--)
    {char ch[5010];
     scanf("%s",ch);
     int i,j,x=0,y=0;
     for(i=0;ch[i]!='\0';i++)
    {if(ch[i]=='A')
         x++;
     else
         y++;
     }
     if(x==2)
     {printf("A\n");continue;
     }
     if(y==2)
    {printf("B\n");continue;
    }
     if(x==1 || y==1)
     {printf("-1\n");continue;
     }
     for(j=0;j<i;j++)
     {int ans=0;
     while(ch[j]!='A' && j<i)
     {ans++;
         j++;
     }
      if(ans==2)
      {for(x=0;x<j-2;x++)
       {if(ch[x]=='A')
          printf("%c",ch[x]);
       }
       printf("B");
       for(x=j;x<i;x++)
       {if(ch[x]=='A')
          printf("%c",ch[x]);
           
       }
         printf("\n");
       j=-1;
      }
      if(j==-1)
          break;
     }
     if(j==-1)
         {continue;
         }
      for(j=0;j<i;j++)
     {int ans=0;
     while(ch[j]!='B' && j<i)
     {ans++;
         j++;
     }
      if(ans==2)
      {for(x=0;x<j-2;x++)
       {if(ch[x]=='B')
          printf("%c",ch[x]);
       }
       printf("A");
       for(x=j;x<i;x++)
       {if(ch[x]=='B')
          printf("%c",ch[x]);
           
       }
       printf("\n");
       j=-1;
      }
      if(j==-1)
          break;
     }
     if(j==-1)
         {continue;
         }
     printf("-1\n");
    }
        return 0;
    }