Problem Statement
Contest Source
Author, Tester and Editorialist : Rohail Alam
DIFFICULTY:
Easy
PREREQUISITES:
None
PROBLEM:
We are being asked to find the longest possible “table” that can be obtained from a string through removal of a finite number(even zero) of characters.
QUICK EXPLANATION:
You will just need to find the first occurrence of “/”, the last occurrence of "" and the length of the table will be nothing but the number of stars between them plus 2 (including the width of the legs)
EXPLANATION:
The above paragraph is pretty much how you approach this problem, but of course you will need to watch out for edge cases. You need to ensure that the first occurrence of “/” is present before the last occurrence of "", else it would not be possible to obtain a table at all since we are not allowed to re-arrange the characters of the string. In addition to this, you must make sure that there is at least one * in between the “/” and “" characters otherwise the definition of a “table” (mentioned in the first paragraph of the problem statement” is not followed.
SOLUTION
Click Me
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
cin>>s;
int n = (int)s.size();
int front=-1,back=-1;
for(int i=0;i<n;++i){
if(s[i]=='/'){
front = i; // Finding the first occurence of "/"
break;
}
}
for(int i = n-1; i<=0;--i){
if(s[i]=='\\'){
back = i; // Finding the last occurence of "\"
break;
}
}
if(front == -1 || back == -1 || front>back){ // Ensuring that there is at least one of both the mentioned characters,
cout<<-1<<endl; // as well checking if the first occurence of "/" precedes the last occurence of "\"
return 0;
}
int stars = 0;
for(int i= front;i<back;++i){
stars+=(s[i]=='*'); // Counting the number of "*" between the first "/" and the last "\"
}
(stars==0)? cout<<-1<<endl : cout<<stars+2<<endl; // If no stars were found then a table cannot be made
}