Given a binary string S containing N characters, the task is to find the maximum distance between two adjacent 1’s.
Examples:
Input: S = “1010010”
Output: 3
Explanation: There are 2 sets of adjacent 1’s in the given index on the indices {0, 2} and {2, 5}.
The one with the maximum distance among them is {2, 5} with a distance of 3 units.Input: S = “100000”
Output: -1
Explanation: No set of adjacent 1’s exist in the given string.
Naive Approach:
The naive approach is to use two nested loops to find the distance between each adjacent 1’s. On getting the adjacent ones, update the maximum distance with the max of the previous maximum and current distance between the ones.
Algorithm:
1. Create a function to find the maximum distance between two adjacent 1’s, that takes a binary string S as input.
2. Initialize variables maxDist to -1.
3. Traverse the string S:
a. If the current character is 1:
Traverse the string S from the current index to the end:
If the next character is 1:
i. Calculate the distance between the current and next 1.
ii. Update the maximum distance if the current distance is greater than the previous maximum.
iii. Break out of the inner loop as we have found the next 1.
4. Return the maximum distance.
Below is the implementation of the approach:
C++
// C++ code for the approach #include<bits/stdc++.h> using namespace std; // function to find maximum distance between two adjacent 1's int maxDistance(string s) { int n = s.length(); int maxDist = -1; for ( int i=0; i<n; i++) { // if current character is 1 if (s[i] == '1' ) { for ( int j=i+1; j<n; j++) { // if next character is also 1 if (s[j] == '1' ) { // calculate distance between current and next 1 int dist = j - i; // update maximum distance and break maxDist = max(maxDist, dist); break ; } } } } // return maximum distance return maxDist; } int main() { string S = "1010010" ; // Function call cout << maxDistance(S) << endl; return 0; } |
Java
import java.io.*; class GFG { // Function to find the maximum distance between two adjacent '1's public static int maxDistance(String s) { int n = s.length(); int maxDist = - 1 ; for ( int i = 0 ; i < n; i++) { // If current character is '1' if (s.charAt(i) == '1' ) { for ( int j = i + 1 ; j < n; j++) { // If next character is also '1' if (s.charAt(j) == '1' ) { // Calculate the distance between current and next '1' int dist = j - i; // Update the maximum distance and break maxDist = Math.max(maxDist, dist); break ; } } } } return maxDist; } public static void main (String[] args) { String S = "1010010" ; // Function call System.out.println(maxDistance(S)); } } // code contributed by shinjanpatra |
Python
def maxDistance(s): n = len (s) max_dist = - 1 i = 0 while i < n: # If current character is '1' if s[i] = = '1' : j = i + 1 # Find the next '1' while j < n: if s[j] = = '1' : # Calculate the distance between current and next '1' dist = j - i # Update the maximum distance and break max_dist = max (max_dist, dist) break j + = 1 i = j else : i + = 1 # Return the maximum distance return max_dist # Main function if __name__ = = "__main__" : S = "1010010" # Function call print (maxDistance(S)) |
C#
using System; class Program { // Function to find maximum distance between two adjacent 1's static int MaxDistance( string s) { int n = s.Length; int maxDist = -1; for ( int i = 0; i < n; i++) { // If current character is '1' if (s[i] == '1' ) { for ( int j = i + 1; j < n; j++) { // If next character is also '1' if (s[j] == '1' ) { // Calculate distance between current and next '1' int dist = j - i; // Update maximum distance and break maxDist = Math.Max(maxDist, dist); break ; } } } } // Return maximum distance return maxDist; } static void Main( string [] args) { string S = "1010010" ; // Function call Console.WriteLine(MaxDistance(S)); } } |
Javascript
// Function to find the maximum distance between two adjacent '1's function maxDistance(s) { const n = s.length; let maxDist = -1; for (let i = 0; i < n; i++) { // If current character is '1' if (s.charAt(i) === '1' ) { for (let j = i + 1; j < n; j++) { // If next character is also '1' if (s.charAt(j) === '1' ) { // Calculate the distance between current and next '1' const dist = j - i; // Update the maximum distance and break maxDist = Math.max(maxDist, dist); break ; } } } } return maxDist; } // Test the function const S = "1010010" ; console.log(maxDistance(S)); |
3
Time Complexity: O(N*N) as two nested loops are executing. Here, N is size of input binary string.
Space Complexity: O(1) as no extra space has been used.
Approach: The given problem is an implementation-based problem. The idea is to store all the indices of 1’s in increasing order in a vector. Hence it can be observed that the required answer will be the maximum of the difference of consecutive integers in the index vector.
Below is the implementation of the above approach:
C++14
// C++ program of the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum // distance between two adjacent // 1's in a given binary string int maxDist(string S) { // Stores the required answer int maxLen = INT_MIN; // Vector to store indices vector< int > indices; // Loop to traverse string for ( int i = 0; i < S.length(); i++) { if (S[i] == '1' ) indices.push_back(i); } // Loop to reverse the // index vector for ( int i = 1; i < indices.size(); i++) // Update maximum distance maxLen = max(maxLen, indices[i] - indices[i - 1]); // Return Answer return maxLen == INT_MIN ? -1 : maxLen; } // Driver Code int main() { string S = "1010010" ; cout << maxDist(S); return 0; } |
Java
// Java program of the above approach import java.io.*; import java.util.*; class GFG { // Function to find the maximum // distance between two adjacent // 1's in a given binary String public static int maxDist(String S) { // Stores the required answer int maxLen = Integer.MIN_VALUE; // Vector to store indices Vector<Integer> indices = new Vector<Integer>(); // Loop to traverse String for ( int i = 0 ; i < S.length(); i++) { if (S.charAt(i) == '1' ) indices.add(i); } // Loop to reverse the // index vector for ( int i = 1 ; i < indices.size(); i++) // Update maximum distance maxLen = Math.max(maxLen, indices.get(i) - indices.get(i - 1 )); // Return Answer return maxLen == Integer.MIN_VALUE ? - 1 : maxLen; } // Driver Code public static void main (String[] args) { String S = "1010010" ; System.out.println(maxDist(S)); } } // This code is contributed by subhamsingh10. |
Python3
# Python code for the above approach # Function to find the maximum # distance between two adjacent # 1's in a given binary string def maxDist(S): # Stores the required answer maxLen = 10 * * - 9 # Vector to store indices indices = [] # Loop to traverse string for i in range ( len (S)): if S[i] = = "1" : indices.append(i) # Loop to reverse the # index vector for i in range ( 1 , len (indices)): # Update maximum distance maxLen = max (maxLen, indices[i] - indices[i - 1 ]) # Return Answer return - 1 if (maxLen = = 10 * * - 9 ) else maxLen # Driver Code S = "1010010" print (maxDist(S)) # This code is contributed by gfgking |
C#
// C# program for above approach using System; using System.Collections.Generic; public class GFG { // Function to find the maximum // distance between two adjacent // 1's in a given binary string static int maxDist( string S) { // Stores the required answer int maxLen = Int32.MinValue; // Vector to store indices List< int > indices = new List< int >(); // Loop to traverse string for ( int i = 0; i < S.Length; i++) { if (S[i] == '1' ) indices.Add(i); } // Loop to reverse the // index vector for ( int i = 1; i < indices.Count; i++) // Update maximum distance maxLen = Math.Max(maxLen, indices[i] - indices[i - 1]); // Return Answer if (maxLen == Int32.MinValue) return -1; else return maxLen; } // Driver code static public void Main () { string S = "1010010" ; Console.WriteLine(maxDist(S)); } } // This code is contributed by hrithikgarg03188 |
Javascript
<script> // JavaScript code for the above approach // Function to find the maximum // distance between two adjacent // 1's in a given binary string function maxDist(S) { // Stores the required answer let maxLen = Number.MIN_VALUE; // Vector to store indices let indices = []; // Loop to traverse string for (let i = 0; i < S.length; i++) { if (S[i] == '1') indices.push(i); } // Loop to reverse the // index vector for (let i = 1; i < indices.length; i++) // Update maximum distance maxLen = Math.max(maxLen, indices[i] - indices[i - 1]); // Return Answer return maxLen == Number.MIN_VALUE ? -1 : maxLen; } // Driver Code let S = "1010010" ; document.write(maxDist(S)); // This code is contributed by Potta Lokesh </script> |
3
Time Complexity: O(N)
Auxiliary Space: O(N) where N is the length of the Binary String.
Space-Efficient Approach: The above approach can also be implemented without using any extra space (vector). The only change is to achieve maximum distance by rigorous difference storing and updation every time we found 1 in the binary string.
C++14
// C++ program of the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum // distance between two adjacent // 1's in a given binary string int maxDist(string S) { // Stores the required answer int maxLen=0,i,start=0; // Loop to find first occurrence of '1' string for ( i = 0; i < S.length(); i++) { if (S[i] == '1' ) { start=i; break ; } } // Loop to traverse remaining // indices of character '1' for (; i < S.length(); i++){ // Update maximum distance if (S[i] == '1' ) { maxLen=max(maxLen,i-start); start=i; } } // Return Answer return maxLen == 0 ? -1 : maxLen; } // Driver Code int main() { string S = "100000" ; cout << maxDist(S); return 0; } |
Java
// Java program of the above approach import java.util.*; class GFG{ // Function to find the maximum // distance between two adjacent // 1's in a given binary String static int maxDist(String S) { // Stores the required answer int maxLen= 0 ,i,start= 0 ; // Loop to find first occurrence of '1' String for ( i = 0 ; i < S.length(); i++) { if (S.charAt(i) == '1' ) { start=i; break ; } } // Loop to traverse remaining // indices of character '1' for (; i < S.length(); i++){ // Update maximum distance if (S.charAt(i) == '1' ) { maxLen=Math.max(maxLen,i-start); start=i; } } // Return Answer return maxLen == 0 ? - 1 : maxLen; } // Driver Code public static void main(String[] args) { String S = "100000" ; System.out.print(maxDist(S)); } } // This code contributed by Rajput-Ji |
Python3
# Python program of the above approach # Function to find the maximum # distance between two adjacent # 1's in a given binary String def maxDist(S): # Stores the required answer maxLen = 0 ; start = 0 ; # Loop to find first occurrence of '1' String for i in range ( len (S)): if (S[i] = = '1' ): start = i; break ; # Loop to traverse remaining # indices of character '1' for i in range (start, len (S)): # Update maximum distance if (S[i] = = '1' ): maxLen = max (maxLen, i - start); start = i; # Return Answer if (maxLen = = 0 ): return - 1 ; else : return maxLen; # Driver Code if __name__ = = '__main__' : S = "100000" ; print (maxDist(S)); # This code contributed by Rajput-Ji |
C#
// C# program of the above approach using System; public class GFG { // Function to find the maximum // distance between two adjacent // 1's in a given binary String static public int maxDist(String S) { // Stores the required answer int maxLen = 0, i, start = 0; // Loop to find first occurrence of '1' String for (i = 0; i < S.Length; i++) { if (S[i] == '1' ) { start = i; break ; } } // Loop to traverse remaining // indices of character '1' for (; i < S.Length; i++) { // Update maximum distance if (S[i] == '1' ) { maxLen = Math.Max(maxLen, i - start); start = i; } } // Return Answer return maxLen == 0 ? -1 : maxLen; } // Driver Code public static void Main(String[] args) { String S = "100000" ; Console.Write(maxDist(S)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // javascript program of the above approach // Function to find the maximum // distance between two adjacent // 1's in a given binary String function maxDist( S) { // Stores the required answer var maxLen = 0, i, start = 0; // Loop to find first occurrence of '1' String for (i = 0; i < S.length; i++) { if (S.charAt(i) == '1 ') { start = i; break; } } // Loop to traverse remaining // indices of character ' 1 ' for (; i < S.length; i++) { // Update maximum distance if (S.charAt(i) == ' 1') { maxLen = Math.max(maxLen, i - start); start = i; } } // Return Answer return maxLen == 0 ? -1 : maxLen; } // Driver Code var S = "100000" ; document.write(maxDist(S)); // This code is contributed by Rajput-Ji </script> |
-1
Time Complexity: O(N)
Auxiliary Space: O(1), where N is the length of the Binary String.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!