Subsequence Equality

Hey guys,
This problem I have taken from www.codechef.com to speed up our coding practice skills and now regularly add a new problem with its solution to clear our Java concept and sharp our logical skills.

Problem : 
Chef Tobby is playing a rapid fire with Bhuvan. He gives Bhuvan a string S and each time, Bhuvan has to guess whether there exists 2 equal subsequences in the string or not.
Bhuvan got a perfect score in the game with Chef Tobby. However, Chef Tobby has now asked Bhuvan to write a program that will do this automatically given a string S. Bhuvan is an intelligent man but he does not know how to write a code. Can you help him?
Find two different subsequences such that they are equal in their value, more formally, find two sequences of indices (a1, a2, ..., ak-1, ak) and (b1, b2, ..., bk-1, bk) such that:
  1. 1≤ ai, bi ≤ |S|
  2. ai < ai+1 for all valid i
  3. bi < bi+1 for all valid i
  4. Sai = Sbi for all valid i
  5. there exist at least one i such that ai is not equal to bi

Input section

The first line contains T, the number of test cases.
Each of the next T lines contain one string S each.
Input will only consist of lowercase english characters

Output section

For each test case, output "yes" or "no" (without quotes) as the solution to the problem.

Input constraints

1 ≤ T ≤ 1000
1 ≤ length of S ≤ 100

Sample Input

4
likecs
venivedivici
bhuvan
codechef

Sample Output

no
yes
no
yes
Solution :
import java.util.*;
public class SolveChecf {
 public static void main(String a[]) {
  Scanner sb = new Scanner(System.in);
  int T;
  String s;
  System.out.println("Generate number of test cases :");
  T = sb.nextInt();
  for (int k = 0; k < T; k++) {
   System.out.println("Enter String s:");
   s = sb.next();
   String bol = "no";
   for (int i = 0; i < s.length(); i++) {
    for (int j = 0; j < s.length(); j++) {
     if (s.charAt(i) == s.charAt(j) && i < j) {
      bol = "yes";
     }
    }
   }
   System.out.println(bol);
  }
 }

}

Comments

Popular posts from this blog

Secure Database Connectivity in node.js with mysql

Export data from mysql db to csv file using java

API (Application Programming Interface)