https://www.codechef.com/TNP62121/problems/TNP602

#PROBLEM LINK: CodeChef: Practical coding for everyone

Author: Setter’s name

Tester:Tester’s name

Editorialist:Editorialist’s name

DIFFICULTY : EASY

#PREREQUISITES : NIL

#PROBLEM :

Goku is given a sequence of 1s and 0s of length N. He is given a task to find a subsequence from the given sequence. There are certain conditions to be met. He should remove one character from the given sequence, the resulting sequence should not contain any 0s, and the length of the resulting sequence found should be maximum. He should tell the length of the subsequence he found.

#SOLUTION :

#include <bits/stdc++.h>
#include
using namespace std;

int longestSubarray(string s)
{
// Add ‘0’ at the end
s += ‘0’;

// Iterator to traverse the string
int i;

// Stores maximum length
// of required substring
int res = 0;

// Stores length of substring of '1'
// preceding the current character
int prev_one = 0;

// Stores length of substring of '1'
// succeeding the current character
int curr_one = 0;

// Counts number of '0's
int numberOfZeros = 0;

// Traverse the string S
for (i = 0; i < s.length(); i++) {

    // If current character is '1'
    if (s[i] == '1') {

        // Increase curr_one by one
        curr_one += 1;
    }

    // Otherwise
    else {

        // Increment numberofZeros by one
        numberOfZeros += 1;

        // Count length of substring
        // obtained y concatenating
        // preceding and succeeding substrings of '1'
        prev_one += curr_one;

        // Store maximum size in res
        res = max(res, prev_one);

        // Assign curr_one to prev_one
        prev_one = curr_one;

        // Reset curr_one
        curr_one = 0;
    }
}

// If string contains only one '0'
if (numberOfZeros == 1) {
    res -= 1;
}

// Return the answer
return res;

}

int main()
{
int T;
cin>>T;
for(int i = 0; i < T; i++){
int N;
string S;
cin>>N;
cin>>S;
cout << longestSubarray(S)<<”\n”;
}
return 0;
}

#EXPLANATION :

Here, in simple words, the question is to find the length of the longest sequence of 1s only from a sequence after the removal of an element from the original sequence.

Method 1: The idea is to traverse the string and search for ‘0’s in the given string. For every character which is found to be ‘0’, add the length of its adjacent substrings of ‘1’. Print the maximum of all such lengths obtained.

Method 2: Alternate approach to solve the problem is to use sliding window technique for finding the maximum length of substring containing only ‘1’s after deleting a single character. Follow the steps below to solve the problem:

Initialize 3 integer variables i, j, with 0 and k with 1
Iterate over the characters of the string S.
For every character traversed, check if it is ‘0’ or not. If found to be true, decrement k by 1.
If k < 0 and character at ith index is ‘0’, increment k and i by one
Increment j by one.
Finally, print the length j – i – 1 after complete traversal of the string.