Given a binary string, the task is to print the length of the longest substring containing only ‘1’.
Examples:
Input: 110
Output: 2
Explanation: Length of the longest substring containing only ‘1’ is “11”.Input: 11101110
Output: 3
Approach: Traverse the string and count the number of contiguous 1‘s encountered. Store the maximum number of contiguous 1s in a variable, say max. Finally, print the value of max obtained.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find length of// longest substring containing '1'int maxlength(string s){ int n = s.length(), i, j; int ans = 0; for (i = 0; i <= n - 1; i++) { // Count the number of contiguous 1's if (s[i] == '1') { int count = 1; for (j = i + 1; j <= n - 1 && s[j] == '1'; j++) count++; ans = max(ans, count); } } return ans;}// Driver Codeint main(){ string s = "11101110"; cout << maxlength(s) << endl; return 0;} |
Java
// Java program to find length// of longest substring containing '1'class GFG { // Function to find length of // of longest substring containing '1' static int maxlength(String s) { int n = s.length(), i, j; int ans = 0; for (i = 0; i <= n - 1; i++) { // Count the number of contiguous 1's if (s.charAt(i) == '1') { int count = 1; for (j = i + 1; j <= n - 1 && s.charAt(j) == '1'; j++) count++; ans = Math.max(ans, count); } } return ans; } public static void main(String[] args) { String s = "11101110"; System.out.println( "Length of longest substring containing '1' = " + maxlength(s)); }} |
Python3
# Python program for the above approach# Function to find length of# longest substring containing '1'def maxlength(s): n = len(s) ans = 0; for i in range(n): # Count the number of contiguous 1's if (s[i] == '1'): count = 1 j = i + 1 while(j <= n - 1 and s[j] == '1'): count += 1 j += 1 ans = max(ans, count) return ans# Driver Codes = "11101110";print(maxlength(s))# This code is contributed by Shivani |
C#
// C# program for the above approachusing System;class GFG{// Function to find length of// of longest substring containing '1'static int maxlength(String s){ int n = s.Length, i, j; int ans = 0; for(i = 0; i <= n - 1; i++) { // Count the number of contiguous 1's if (s[i] == '1') { int count = 1; for(j = i + 1; j <= n - 1 && s[j] == '1'; j++) count++; ans = Math.Max(ans, count); } } return ans;}// Driver codepublic static void Main(String[] args){ String s = "11101110"; Console.Write(maxlength(s));}}// This code is contributed by shivanisinghss2110 |
Javascript
<script> // JavaScript program for the above approach; // Function to find length of // longest substring containing '1' function maxlength(s) { let n = s.length, i, j; let ans = 0; for (i = 0; i <= n - 1; i++) { // Count the number of contiguous 1's if (s[i] == '1') { let count = 1; for (j = i + 1; j <= n - 1 && s[j] == '1'; j++) count++; ans = Math.max(ans, count); } } return ans; } // Driver Code let s = "11101110"; document.write(maxlength(s));// This code is contributed by Potta Lokesh </script> |
Output
3
Time Complexity: O(N2)
Auxiliary Space: O(1)
Counting Approach:
Follow the steps to implement the approach:
- Initialize two variables, count and maxCount, to 0.
- Iterate through the string from left to right.
- If the current character is ‘1’, increment count by 1.
- If the current character is ‘0’, update maxCount to the maximum of count and maxCount, and reset count to 0.
- After the iteration, update maxCount to the maximum of count and maxCount again.(if the substring containing only ‘1’ is in the end of the string.)
- The updated maxCount is the length of the longest substring containing only ‘1’.
Below is the implementation:
C++
// C++ Program To Implement the above approach#include <iostream>#include <string>using namespace std;// Function to implement the counting approachint longestSubstringLength(string Str) { // initialize variable int count = 0; int maxCount = 0;// iterate over the string from left to right for (char c : Str) { // if current character is '1' then increment count if (c == '1') { count++; } else {//otherwese store maximum count because it is maximum length till now maxCount = max(count, maxCount); count = 0; } }// if sub-string found at the end of the string maxCount = max(count, maxCount); return maxCount;}// Driver Codeint main() { string Str = "11101110"; cout<< longestSubstringLength(Str)<<endl; return 0;}// This code is contributed by Veerendra_Singh_Rajpoot |
Java
public class GFG { // Function to implement the counting approach public static int longestSubstringLength(String str) { // initialize variables int count = 0; int maxCount = 0; // iterate over the string from left to right for (char c : str.toCharArray()) { // if current character is '1' then increment // count if (c == '1') { count++; } else { // otherwise, store the maximum count // because it is the maximum length so // far maxCount = Math.max(count, maxCount); count = 0; } } // if a sub-string is found at the end of the string maxCount = Math.max(count, maxCount); return maxCount; } // Driver code public static void main(String[] args) { String str = "11101110"; System.out.println(longestSubstringLength(str)); }}// This code is contributed by Veerendra_Singh_Rajpoot |
Python3
# Function to implement the counting approachdef longest_substring_length(s): # Initialize variables count = 0 max_count = 0 # Iterate over the string from left to right for c in s: # If the current character is '1', then increment count if c == '1': count += 1 else: # Otherwise, store the maximum count because it is the maximum length till now max_count = max(count, max_count) count = 0 # If a sub-string is found at the end of the string max_count = max(count, max_count) return max_count# Driver Codeif __name__ == "__main__": Str = "11101110" print(longest_substring_length(Str)) |
C#
using System;class Program{ static int LongestSubstringLength(string str) { int count = 0; int maxCount = 0; foreach (char c in str) { if (c == '1') { count++; } else { maxCount = Math.Max(count, maxCount); count = 0; } } maxCount = Math.Max(count, maxCount); return maxCount; } static void Main() { string str = "11101110"; Console.WriteLine(LongestSubstringLength(str)); }} |
Javascript
// JS Program To Implement the above approach// Function to implement the counting approachfunction longestSubstringLength(Str) { // initialize variable let count = 0; let maxCount = 0;// iterate over the string from left to right for (let c of Str) { // if current character is '1' then increment count if (c == '1') { count++; } else {//otherwese store maximum count because it is maximum length till now maxCount = Math.max(count, maxCount); count = 0; } }// if sub-string found at the end of the string maxCount = Math.max(count, maxCount); return maxCount;}// Driver Codelet Str = "11101110";console.log(longestSubstringLength(Str)); |
Output
3
Time Complexity: O(n), where n is the length of the binary string.
Space Complexity: O(1).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Find More on to that Topic: geeksforgeeks.org/longest-substring-containing-1/ […]
… [Trackback]
[…] Read More on to that Topic: geeksforgeeks.org/longest-substring-containing-1/ […]