You are not logged in. Please login at www.codechef.com to post your questions!

×

LIKECS01 - Editorial

Problem Link

Practice

Contest

Author: Bhuvnesh Jain

Tester: Hasan Jaddouh

Editorialist: Bhuvnesh Jain

Difficulty

CAKEWALK

Prerequisites

Looping Techniques

Problem

You are given a string $S$ and you are required to find whether there exists $2$ different non-empty subsequences in $S$ which are equal.

Quick Explanation

Check whether there exist 2 equal characters in the string.

Explanation

Lemma : If there exists a solution, then the smallest such equal subsequences will be of length 1.

Proof : Let us assume the solution exists and the length of smallest equal subsequence is greater than $1$. Let the subsequences be $a$ and $b$. Since they are equal, they should be of same length and each character should be same on every index. Since, the 2 subsequence should differ by atleast one index, but the subsequence being equals means that we get a smaller subsequence of length $1$ which is also equal contradicting our assumption. Hence, the lemma is correct.

Now, to implement the above claim, we can simply loop over all the possible pair of positions and check if they are equal or not. The complexity of the above approach will be $O(N^2)$, which is sufficient to pass the problem.

Actually, the above solution can be made more efficient by simply creating a frequency array of size 26 (or equivalently Alphabet size) and storing the count of every character in it. The answer exist if the frequency of any alphabet is more than 1. The complexity of this approach is $O(N + ALPHABET)$.

Bonus problem

What is the smallest length of string required to be sure that answer will be always "yes" irrespective of the string?

Time Complexity

$O(N^2)$ or $O(N + ALPHABET)$, where $N = $ length of string.

Space Complexity

$O(N)$

Solution Links

Setter's solution

Tester's solution

This question is marked "community wiki".

asked 12 Sep '17, 22:44

likecs's gravatar image

6★likecs
3.7k2481
accept rate: 9%

edited 18 Sep '17, 22:51

1

The two subsequences might have common elements, so in the proof of the lemma it should be the character at index $i$ such that $a_i \neq b_i$, which is guaranteed to exist and is not necessarily the first.

(18 Sep '17, 01:27) eugalt3★

What is the smallest length of string required to be sure that answer will be always "yes" irrespective of the string?

27?

link

answered 18 Sep '17, 00:38

goan_22's gravatar image

4★goan_22
363
accept rate: 33%

Which is why the bonus question says "irrespective of the string". In the other cases, the answer will obviously be less than 27.

(18 Sep '17, 01:15) goan_224★

"Because if all characters have to be distinct, then you cannot have a string of length 27 with all distinct"

That is exactly what the bonus q asks.

If you want the string to simply repeat a single character, then the smallest string required for answer to be yes would be 2. For eg: "aa".

(18 Sep '17, 01:27) goan_224★

Damn, I messed up. I, for some reason, understood it as it as "String a has a sub sequence of String b" and was really confused. (Which is why i mentioned 2 strings in that answer, lol)

(18 Sep '17, 01:30) vijju123 ♦♦5★

Absolutely

27 is the minimum length to guarantee the answer "yes" because of pigeon-hole principle which you may read at following link...

https://en.wikipedia.org/wiki/Pigeonhole_principle

(18 Sep '17, 01:31) taran_14075★

Can we say that the Time Complexity will never be greater than 26 i.e no of total alphabets. thus Time Complexity O(N + Albhabet)<O(26). As we can can but a condition that :

if(string.length()>26)
 { cout<<"yes"<<endl;
   continue;   //goes to next loop
 }

Thus, bonus Q-> min length of string required is 27 for ans to be always "yes" irrespective of any string you give as input.

link

answered 18 Sep '17, 00:48

dj21514's gravatar image

2★dj21514
112
accept rate: 0%

edited 18 Sep '17, 00:50

I thought this but said naah , it can't be that easy .

link

answered 18 Sep '17, 00:28

trashmaster's gravatar image

2★trashmaster
98619
accept rate: 12%

If over 200 people can solve it in the first 5 minutes, it should be easy right? :p

(18 Sep '17, 00:48) nileshjha192★

i guess i am suffering from low confidence since previous long challenge .

(18 Sep '17, 01:17) trashmaster2★

Ohh same here buddy!

(18 Sep '17, 02:54) nileshjha192★

Mysolution

import java.io.; import java.util.; class Codechef1 { public static void main(String args[]) { Scanner sc=new Scanner(System.in); int T=sc.nextInt(); int i; int l; for(i=0;i<t;i++) {="" string="" s="sc.next();" l="s.length()-1;" int="" j;="" hashset<character=""> hset=new HashSet<character>(); for(j=0;j<=l;j++) { hset.add(s.charAt(j)); } System.out.println(hset); if(hset.size()==s.length()) { System.out.println("No"); } else if(hset.size()-2<s.length()); { System.out.println("yes"); } } } }

Happycoding

link

answered 18 Sep '17, 18:49

aakash30's gravatar image

2★aakash30
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,875
×1,695
×593
×99
×8

question asked: 12 Sep '17, 22:44

question was seen: 2,581 times

last updated: 23 Sep '17, 22:07