Problem Link - CodeChef: Practical coding for everyone
Author - amarnathsama
Tester - amarnathsama
Editorilist - apurv001
IDEA
Find the maximum length of a substring of string s that starts with Z and ends with A.
This is the problem.
For simple consideration, it is best to use Z as close to the beginning as possible and B as late as possible.
For the case of -1
We just need to check 4 cases:
Case 1: If Z is not in the string
Case 2: If A is not in the string
Case 3: If both A and Z are not in the string
Case 4: If first occurrence of Z is after the last occurrence of A
You will find that it is best to choose one that is close to the tail. Each position can be checked with O (| s |)
Code
#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio;
string s;
cin >> s;
int a = -1, z = -1;
for(int i = 0; i < s.size(); i++) {
if(s[i] == 'Z') {
z = i;
break;
}
}
for(int i = s.size() - 1; i >= 0; i--) {
if(s[i] == 'A') {
a = i;
break;
}
}
if(a - z <= 0 || a == -1 || z == -1) {
cout << -1;
}
else {
cout << a - z + 1;
}
return (0);
}