TICKETS5 - Editorial

PROBLEM LINK:

Practice
Contest

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Basics of looping, conditional statements in any language.

PROBLEM:

Given a string s, find whether exactly two different letters alternate in it or not. e.g. if s = “ABABAB”, then the answer will be yes or if s = “ABC”, then the answer would be no, if s = “AA” answer would be no because the alternating characters should be different as stated in the problem.

EXPLANATION:

Given a string, first check the starting two characters, if they are the same (character is in consecutive position instead of alternating) then clearly the answer is NO. Otherwise we just have to check whether the first two characters (i.e. s[0] and s[1]) are occurring in even and odd positions respectively or not.

Pseudo Code

 if(S[0]==S[1]) return false;
 for(i=0; i+2 < N; i++) 
     if(S[i]!= S[i+2]) return false;
 return true;

The above code first checks the first two character and if they are different then check the whole string whether it follows the alternating character condition. The time complexity of the algorithm is \mathcal{O}(|s|) as we are iterating over all the characters of string s only once.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

2 Likes

Consider the test case when the string is : “ABA”
What should be the output of this string?
what does the alternate mean?:- “Pair of characters” should be in alternate for or “Single character” should be in alternate form.

import java.util.*;
class test
{
public void check()
{
Scanner sc=new Scanner(System.in);
System.out.println(“Enter the Stirng pattern”);
String s=sc.nextLine();
int l=s.length();
int i=2;
boolen flag=True;
char c=s.charAt(0);
char cc=s.charAt(1);
if(c!=cc)
{
while(flag!=False)
{
while(i<l)
{
char c1=s.charAt(i);
char c2=s.charAt(i+1);
if((c1!=c2)&&((c1==c)||(c1==cc))&&((c2==c)||(c2==cc)))
flag=True;
else
{
flag=False;
break;
}
i++;
}
}
if(flag==True)
System.out.println(“YES”);
else
System.out.println(“NO”);
}
else
System.out.println(“NO”);
}
}

What is wrong with my code?
Please help someone…
#include<stdio.h>
#include<string.h>
int main()
{
int t,i,len;
char str[101];
scanf("%d",&t);
while(t–)
{
int flag=0;
scanf("%s",str);
len=strlen(str);
for(i=2;i<len;i++)
{
if(i%2==0)
{
if(str[i]==str[0])
{
flag=1;
}
else
{
flag=0;break;
}
}
else if(i%2!=0)
{
if(str[i]==str[1])
flag=1;
else
{
flag=0;break;
}
}
}
if(flag==1)
printf(“YES\n”);
else if(flag==0)
printf(“NO\n”);
}
return 0;
}

it will be true ABABABA format is correct if ABA is incorrect then strlen(s)%2!=0 cases directly gives NO but it;s not the case

if strlen is 1 then it’s true so u can understand it with this case.

but odd length of string should be in test cases

Hi,
for this exercise, i’m running the below code. But it keeps saying wrong answer on all the subtasks. I couldn’t figure out why. Please review.

t = int(input())
for i in range(t):
str = input()
if str[0] == str[1]:
print(‘No’)
else:
x = ‘’.join(set(str[::2]))
y = ‘’.join(set(str[1::2]))
if len(x) > 1 or len(y) > 1:
print(‘No’)
else:
print(‘Yes’)

how to solve it ?? help

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

class CodeChef1 {

public static void main(String[] args) throws IOException {

    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    Integer t = Integer.valueOf(reader.readLine());

    while (t > 0) {

        String s = reader.readLine();

        if(s.charAt(0)==s.charAt(2) && s.charAt(1)==s.charAt(3))

            System.out.println("YES");

        else

            System.out.println("NO");

        t--;

    }  


             
}

}

what is wrong in my code its showing runtime error.why?

I am getting wrong answer for this plz someone tell whats the error

int main()
{
string temp;
long int k,x;
cin>>k;
while(k–){
long int count = 0,count1=0;
cin >> temp;
x=temp.length();

for(int i=0;i<x;i++)

 {if(temp[i]==temp[i+2] && temp[i]!=temp[i+1])
       {count1++;
           break;
             }
else 
   {count++;
      break;
       }  
}

if(count1==0)
cout<<“NO”<<endl;
else if(count==0)
cout<<“YES”<<endl;

} return 0;}

@shivamsst You’re just checking only the first 3 characters of the string to make your decision.

If the string, say s, is “ABABCDCD” your code will print “YES” since
s[0] == s[2] (“A” == “A”) and also s[0] != s[1] (since “A” != “B”)
but you did not check the rest of string if it matches the criteria!

You should follow the pseudo-code given in the editorial. It is clean and compact. You will understand it easily.

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t–)
{
string s;
cin>>s;
char a,b;
int l=s.size(),f=0;
for(int i=0;i<l;i++)
{
if(i==0)
a=s[i];
if(i==1 && s[i]!=a)
b=s[i];
else if(s[i]==a && i==1)
{
f=1;
break;
}
if((i%2!=0 && s[i]!=b)||(i%2==0 && s[i]!=a))
{
f=1;
break;
}
}
if(f==0)
cout<<“YES”;
else
cout<<“NO”;
cout<<endl;
}
return 0;
}

what is wrong in this code not understanding

#include <stdio.h>
int main()
{
int t,i,c;
char s[110];
scanf("%d",&t);
while(t–)
{ scanf("%s",s);
c=0;
int l=strlen(s);
if(l==2&&s[0]!=s[1])
{printf(“YES\n”);}
for(i=0;i<l-2&&l>2;i++)
{
if(s[i]==s[i+2])
c=1;
else{
c=0;
}
if(c==0)
printf(“NO\n”);
break;
}

    if(c==1)
    {
        printf("YES\n");
    }

}
}

Your pseudo code is working wrong, cuz if u use a string for example: ABABABAAAAAAAAAA, then it gives true, which is false.

1 Like

Umm there could be a better approach but it isn’t working and I really don’t know why… My logic was to extract a string from index 0 to 1 and then replace its occurrences in the original string by “”, now if the length of resultant string is empty o/p “YES” else “NO”… here’s my snippet for this :

if(s.length()%2!=0)
return “NO”;
else {
String temp = s.substring(0,2);
s = s.replaceAll(temp, “”);
if(s.length()==0)
return “YES”;
else
return “NO”;
}

but it shows wrong o/p pls help

Your method is actually better.

The only problem is- your code ouputs “NO” for all cases where the length is odd numbered. This is not correct.
Example- “ABA” answer should be YES, but your code gives no. Same goes with ABABA, which should actually give “YES”.

should ABA and ABABAC give YES?

should ABA and ABABAC give YES?